Ola Svensson

I am an Assistant Professor active in the theory group at the School of Computer and Communication Sciences, EPFL. My research interests include approximation algorithms, combinatorial optimization, computational complexity and scheduling.

Phone	+41 21 693 1204
Fax	+41 21 693 7510
E-mail	firstname.lastname at epfl dot ch
Address	EPFL-IC Building INJ (INJ112) Station 14 CH-1015 Lausanne Switzerland
Visiting address	Office INJ112

---

Teaching and Service

Semester projects

• Feedback Arc Set in Tournaments (Masters project)
• Geometric Algorithms for Discrepancy (Bachelors or Masters Project)

Courses

This semester, I am responsible for the graduate course Approximation Algorithms and Hardness of Approximation.
Last semester, I was giving the Nov-Dec lectures in Omid Etesami's undergraduate course Algorithmique. Previously at KTH, I was responsible for the graduate course Approximation Algorithms and I taught some of the lectures in Johan Håstad's postgraduate course Theoreticians toolkit.

Program Committees

I will or have recently served on the program committees of the following conferences: ITCS'14, SODA'14, FSTTCS'13, APPROX'13, MFCS'13, ESA'12, CATS'12.

Publications on Approximability

Journal Papers

• Ola Svensson: Santa Claus Schedules Jobs on Unrelated Machines.
  To appear in SIAM Journal on Computing, 2012
• Florian Diedrich, Klaus Jansen, Lars Prädel, Ulrich M. Schwarz, Ola Svensson: Tight Approximation Algorithms for Scheduling with Fixed Jobs and Non-Availability.
  To appear in Transactions on Algorithms, 2012.
• Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson: Approximating Linear Threshold Predicates.
  To appear in Transactions on Computation Theory, 2012.
• Monaldo Mastrolilli, Ola Svensson: Hardness of Approximating Flow and Job Shop Scheduling Problems.
  Journal version in the Journal of the ACM 58(5): 20:1-20:32, 2011.
  
• Ola Svensson: Hardness of Precedence Constrained Scheduling on Identical Machines.
  Journal version in SIAM J. Comput. 40(5): 1258-1274, 2011.
  
• Christoph Ambühl, Monaldo Mastrolilli, Ola Svensson: Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
  Journal version in SIAM J. Comput. 40(2): 567-596, 2011.
  
• Christoph Ambühl, Monaldo Mastrolilli, Nikos Mutsanas, Ola Svensson: On the Approximability of Single Machine Scheduling with Precedence Constraints.
  Mathematics of Operations Research 36(4): 653-669, 2011.
  
• Monaldo Mastrolilli, Maurice Queyranne, Andreas S. Schulz, Ola Svensson, Nelson A. Uhan: Minimizing the sum of weighted completion times in a concurrent open shop.
  Journal version in Oper. Res. Lett. 38(5): 390-395, 2010.
  

Conference Papers

• Shi Li, Ola Svensson: Approximating k-median via Pseudo-Approximation.
  To appear in the proceedings of the 45th ACM Symposium on the Theory of Computing (STOC), 2013.
  Full version available as arXiv report 1211.0243
  
• Ola Svensson: Hardness of Vertex Deletion and Project Scheduling .
  Extended abstract in APPROX 2012. Invited to ToC special issue
  Full version available as arXiv report 1206.3408.
  
• Lukas Polacek, Ola Svensson: Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation.
  Extended abstract in ICALP 2012.
  Full version available as arXiv report 1205.1373.
  
• Tobias Mömke, Ola Svensson: Approximating Graphic TSP by Matchings.
  Extended abstract in IEEE Symposium on Foundations of Computer Science (FOCS) 2011. Best Paper Award
  Full version available as arXiv report 1104.3090.
  
• Ola Svensson: Santa Claus Schedules Jobs on Unrelated Machines.
  Extended abstract in ACM Symposium on Theory of Computing (STOC) 2011. Invited to SICOMP special issue.
  Full version available as arXiv report 1011.1168.
  
• Klaus Jansen, Lars Prädel, Ulrich M. Schwarz, Ola Svensson: Faster Approximation Algorithms for Scheduling with Fixed Jobs.
  Extended abstract in Computing: the Australasian Theory Symposium (CATS) 2011.
  
• Ola Svensson: Conditional Hardness of Precedence Constrained Scheduling on Identical Machines.
  Extended abstract in ACM Symposium on Theory of Computing (STOC) 2010.
  
• Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson: Approximating Linear Threshold Predicates.
  Extended abstract in APPROX-RANDOM 2010.
  Full version available as ECCC Report TR10-132
  
• Monaldo Mastrolilli, Ola Svensson: Improved Bounds for Flow Shop Scheduling.
  Extended abstract in ICALP 2009.
  
• Monaldo Mastrolilli, Ola Svensson: (Acyclic) JobShops are Hard to Approximate.
  Extended abstract in IEEE Symposium on Foundations of Computer Science (FOCS) 2008.
  
• Monaldo Mastrolilli, Nikolaus Mutsanas, Ola Svensson: Approximating Single Machine Scheduling with Scenarios.
  Extended abstract in APPROX-RANDOM 2008.
  
• Christoph Ambühl, Monaldo Mastrolilli, Ola Svensson: Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling.
  Extended abstract in IEEE Symposium on Foundations of Computer Science (FOCS) 2007.
  
• Christoph Ambühl, Monaldo Mastrolilli, Nikolaus Mutsanas, Ola Svensson: Scheduling with Precedence Constraints of Low Fractional Dimension.
  Extended abstract in IPCO 2007.
  
• Christoph Ambühl, Monaldo Mastrolilli, Ola Svensson: Approximating Precedence-Constrained Single Machine Scheduling by Coloring.
  Extended abstract in APPROX-RANDOM 2006.
  

Surveys

• Christoph Ambühl, Monaldo Mastrolilli, Nikolaus Mutsanas, Ola Svensson: Precedence Constraint Scheduling and Connections to Dimension Theory of Partial Orders
  In the Algorithmics Column by Gerhard J. Woeginger of the Bulletin of the European Association for Theoretical Computer Science (EATCS) , number 95, 2008.

Theses

• Ola Svensson: Approximability of Some Classical Graph and Scheduling Problems.
  PhD Thesis, IDSIA - Universita della Svizzera italiana, 2009.
  PDF version available here.
  
• Ola Svensson: Linear Programming and Linear Complementarity Methods for Infinite Games.
  Master Thesis, Uppsala University, 2005.
  

Publications on Algorithms for Infinite Games from my Master thesis

• Ola Svensson, Sergei Vorobyov: Linear Complementarity and P-matrices for Stochastic Games
  In proceedings of PSI 2006.
• Ola Svensson, Sergei Vorobyov: Linear Programming Polytope and Algorithm for Mean Payoff Games
  In proceedings of AAIM, 2006.
• Ola Svensson: Mean Payoff Games and Linear Complementarity
  In proceedings of ESSLLI, 2005. Rewarded best poster award.

---