Ola Svensson

Email: osven followed by at kth.se Fax: +46 8 790 09 30 Address: Nada, KTH, SE-100 44 Stockholm, Sweden Visiting address: Osquars backe 2, floor 4, room 1444

I am a post-doc working in Johan Håstad's group on approximability. In June 2009, I successfully defended my PhD thesis entitled "Approximability of Some Classical Graph and Scheduling Problems" available here. My supervisor was Monaldo Mastrolilli.

Publications on Approximability

• Approximating Linear Threshold Predicates with Mahdi Cheraghchi, Johan Håstad, and Marcus Isaksson.
  To appear in proceedings of Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2010.
  
  
• Conditional Hardness of Precedence Constrained Scheduling on Identical Machines
  In proceedings of the 42th ACM Symposium on Theory of Computing (STOC), pages 745-754, 2010.
  
  
• Minimizing the sum of weighted completion times in a concurrent open shop with Monaldo Mastrolilli, Maurice Queyranne, Andreas S. Schuls and Nelson A. Uhan.
  Accepted for publication in Operations Research Letters, 2010.
  
  
• Improved Bounds for Flow Shop Scheduling with Monaldo Mastrolilli.
  In proceedings of International Colloquium on Automata, Languages and Programming (ICALP), pages 677-688, 2009.
  
  
• (Acyclic) Job Shops are Hard to Approximate with Monaldo Mastrolilli.
  In proceedings of IEEE Symposium on Foundations of Computer Science (FOCS), pages 583-592, 2008.
  
  
• Approximating Single Machine Scheduling with Scenarios with Monaldo Mastrolilli and Nikos Mutsanas.
  In proceedings of Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 153-164, 2008.
  
  
• Approximating Scheduling with with Precedence Constraints of Low Fractional Dimension with Christoph Ambuhl, Monaldo Mastrolilli and Nikos Mutsanas.
  In proceedings of Integer Programming and Combinatorial Optimization (IPCO), pages 130-144, 2007.
  
  
• Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence-Constrained Scheduling with Christoph Ambuhl and Monaldo Mastrolilli.
  In proceedings of IEEE Symposium on Foundations of Computer Science (FOCS), pages 329-337, 2007.
  
  
• Approximating Precedence-Constrained Scheduling by Coloring with Christoph Ambuhl and Monaldo Mastrolilli.
  In proceedings of Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 15-26, 2006.

Up to Start.