Ola Svensson

I am a post-doc at the Algorithmics Laboratory of the School of Computer and Communication Sciences Computer Science of EPFL. My research interests include approximation algorithms, combinatorial optimization, computational complexity and scheduling. For more information please see my CV.

Teaching and Service

This academic year, I taught some of the lectures in Amin Shokrollahi's undergraduate course Algorithmique. Last year, I was responsible for the postgraduate course Approximation Algorithms and I taught some of the lectures in Johan Håstad's postgraduate course Theoreticians toolkit. The last two courses were given while I was a post-doc at the KTH Royal Institute of Technology.

This academic year, I will serve on the program committees of the following conferences:

• Design and Analysis Track of the 20th European Symposium on Algorithms (ESA) 2012.
• The 18th Computing: the Australasian Theory Symposium (CATS) 2012.

Publications on Approximability

Journal Papers

• Klaus Jansen, Lars Prädel, Ulrich M. Schwarz, Ola Svensson: Faster Approximation Algorithms for Scheduling with Fixed Jobs.
  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

• Tobias Mömke, Ola Svensson: Approximating Graphic TSP by Matchings.
  To appear 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.
  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.
  

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.