Ola Svensson

I am an Associate 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. I am grateful to the generous support from the ERC Starting Grant "OptApprox" (2014-2019) and from the SNF grant "Randomness in Problem Instances and Randomized Algorithms" (2019 - 2023).

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

---

Supervision

I have (and had) the pleasure to advice and learn from the following PhD students:

• Christos Kalaitzis (2012 - 2016, now postdoc at ETHZ)
• Abbas Bazzi (2013 - 2017, now at Google Zürich)
• Ashkan Norouzi-Fard (2013 - 2018, now at Google Zürich)
• Jakub Tarnawski (2014 - 2019, now at MSR)
• Buddhima Gamlath (2016 - )
• Paritosh Garg (2017 - , coadvised with Michael Kapralov)
• Etienne Bamas (2019 - )
• Xinrui Jia (2019 - )
• Andreas Maggiori (2019 - , coadvised with Ruediger Urbanke)

Teaching and Service

I am very proud to have received the I&C teaching award.

Semester projects

For available semester projects for EPFL students, please contact me directly be sending an email.

Courses

I teach (taught) Advanced Algorithms, Algorithms, Topics in Theoretical Computer Science., Computational Complexity, and Approximation Algorithms and Hardness of Approximation.
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'21, ESA'19 (chair), FOCS'18, APPROX'17, FOCS'16, SWAT'16, STOC'15, WAOA'14 (co-chair), STOC'14, ITCS'14, SODA'14, FSTTCS'13, APPROX'13, MFCS'13, ESA'12, CATS'12.

Publications

Journal Papers

• Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward: Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms
  Journal version in SIAM Journal on Computing 49(4), 2020.
• Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta, and Ola Svensson: No Small Linear Program Approximates Vertex Cover Within a Factor 2 - epsilon
  Journal version in Math. Oper. Res. 44(1), 147-172, 2019.
• Moran Feldman, Ola Svensson, and Rico Zenklusen: A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
  Journal version in Math. Oper. Res. 43(2), 638-650, 2018.
• Ola Svensson, Jakub Tarnawski, and László A. Végh: Constant factor approximation for ATSP with two edge weights
  Journal version in Math. Program. 172(1-2), 371-397, 2018.
• Abbas Bazzi, Samuel Fiorini, Sangxia Huang, and Ola Svensson: Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits
  Journal version in Theory of Computing 14(1), 1-29, 2018.
• Teklemariam Tsegay Tesfay, Jean-Yves Le Boudec, and Ola Svensson: Optimal Software Patching Plan for PMUs
  Journal version in IEEE Trans. Smart Grid 9(6), 6500-6510, 2018.
• Hyung-Chan An, Mohit Singh, and Ola Svensson: LP-Based Algorithms for Capacitated Facility Location
  Journal version in SIAM Journal on Computing 46(1), 272-306, 2017.
• Hyung-Chan An, Ashkan Norouzi-Fard, and Ola Svensson: Dynamic Facility Location via Exponential Clocks
  Journal version in ACM Transactions on Algorihms 13(2), 21:1- 21:20, 2017.
• Chidambaram Annamalai, Christos Kalaitzis, and Ola Svensson: Combinatorial Algorithm for Restricted Max-Min Fair Allocation
  Journal version in in ACM Transactions on Algorihms 13(3), 37:1- 37:28, 2017.
• Tobias Mömke and Ola Svensson: Removing and Adding Edges for the Traveling Salesman Problem.
  Journal version in the Journal of the ACM 63(1), 2:1-2:28, 2016.
• Shi Li and Ola Svensson: Approximating k-median via Pseudo-Approximation.
  Journal version in SIAM Journal on Computing 45(2), 530-547, 2016.
• Lukas Polacek, Ola Svensson: Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation.
  Journal version in ACM Transactions on Algorihms 12(2), 13:1- 13:13, 2016.
• Ola Svensson: Hardness of Vertex Deletion and Project Scheduling.
  Journal version in Transactions on Computation Theory 9(24):759-781.
• Monaldo Mastrolilli, Nikolaus Mutsanas, and Ola Svensson: Single machine scheduling with scenarios.
  Journal version in Theoretical Computer Science 477:57-66, 2013.
• Ola Svensson: Santa Claus Schedules Jobs on Unrelated Machines.
  Journal version in SIAM Journal on Computing 41(5):1318-1341, 2012
• Florian Diedrich, Klaus Jansen, Lars Prädel, Ulrich M. Schwarz, Ola Svensson: Tight Approximation Algorithms for Scheduling with Fixed Jobs and Non-Availability.
  Journal version in ACM Transactions on Algorithms 8(3):27, 2012.
• Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson: Approximating Linear Threshold Predicates.
  Journal version in Transactions on Computation Theory 4(1):2, 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

• Hendrik Fichtenberger, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson: Consistent k-Clustering for General Metrics.
  In SODA 2021
  Available as arXiv report 2011.06888.
  
• Etienne Bamas, Andreas Maggiori, Ola Svensson: The Primal-Dual method for Learning Augmented Algorithms.
  In NeurIPS 2020, Oral presentation
  Available as arXiv report 2010.11632.
  
• Etienne Bamas, Andreas Maggiori, Lars Rohwedder, Ola Svensson: Learning Augmented Energy Minimization via Speed Scaling.
  In NeurIPS 2020, Spotlight presentation
  Available as arXiv report 2010.11629.
  
• Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, Ola Svensson: Fast and Accurate k-means++ via Rejection Sampling.
  In NeurIPS 2020
  Available here.
  
• Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, Rico Zenklusen: The one-way communication complexity of submodular maximization with applications to streaming and robustness.
  In STOC 2020
  Available as arXiv report 2003.13459.
  
• Xinrui Jia, Kshiteej Sheth, Ola Svensson: Fair Colorful k-Center Clustering.
  In IPCO 2020
  Available as arXiv report 2007.04059.
  
• Paritosh Garg, Sagar Kale, Lars Rohwedder, and Ola Svensson: Robust Algorithms Under Adversarial Injections.
  In ICALP 2020
  Available as arXiv report 2004.12667.
  
• Nikhil Bansal, Ola Svensson, Luca Trevisan: New Notions and Constructions of Sparsification for Graphs and Hypergraphs.
  In FOCS 2019.
  Available as arXiv report 1905.01495.
• Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, David Wajc: Online Matching with General Arrivals.
  In FOCS 2019.
  Available as arXiv report 1904.08255.
• Buddhima Gamlath, Sagar Kale, Slobodan Mitrovic, Ola Svensson: Weighted Matchings via Unweighted Augmentations.
  In PODC 2019.
  Available as arXiv report 1811.02760.
• Buddhima Gamlath, Sagar Kale, Ola Svensson: Beating Greedy for Stochastic Bipartite Matching.
  In SODA 2019.
  
• Ashkan Norouzi-Fard, Jakub Tarnawski, Boba Mitrovic, Amir Zandieh, Aida Mousavifar Mousavifar, Ola Svensson: Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams.
  In ICML 2018.
• Buddhima Gamlath, Sangxia Huang, Ola Svensson: Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering.
  In ICALP 2018.
  Available as arXiv report 1803.00926.
  
• Ola Svensson, Jakub Tarnawski, Laszlo Vegh: A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
  Extended abstract in the 50th ACM Symposium on the Theory of Computing (STOC), 2018. Best paper award.
  Available as arXiv report 1708.04215. For a summary of the approach see the 10-page extended abstract.
• Moran Feldman, Ola Svensson, Rico Zenklusen: A Framework for the Secretary Problem on the Intersection of Matroids
  To appear in ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018.
  Available as arXiv report 1704.02608
  
• Ola Svensson, Jakub Tarnawski: The Matching Problem in General Graphs is in Quasi-NC
  Extended abstract in IEEE Symposium on Foundations of Computer Science (FOCS), 2017. Best paper award.
  Available as arXiv report 1704.01929
  
• Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, Justin Ward: Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms.
  To appear in IEEE Symposium on Foundations of Computer Science (FOCS), 2017. Invited to SICOMP special issue.
  Available as arXiv report 1612.07925
  
• Christos Kalaitzis, Ola Svensson, Jakub Tarnawski: Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios .
  Extended abstract in ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017.
  Available as arXiv report 1607.07631
  
• Abbas Bazzi, Samuel Fiorini, Sangxia Huang, Ola Svensson: Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits .
  Extended abstract in ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017.
  Available as arXiv report 1609.03737
  
• Aditya Bhaskara, Mehrdad Ghadiri, Vahab Mirrokni Ola Svensson: Linear Relaxations for Finding Diverse Elements in Metric Spaces .
  NIPS, 2016.
  
• Nikhil Bansal, Aravind Srinivasan, Ola Svensson: Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines.
  Extended abstract in the 48th ACM Symposium on the Theory of Computing (STOC) , 2016. Invited to SICOMP special issue.
  Available as arXiv report 1511.07826
  
• Ola Svensson, Jakub Tarnawski, Laszlo Vegh: Constant Factor Approximation for ATSP with Two Edge Weights.
  Extended abstract in the 18th Conference on Integer Programming and Combinatorial Optimization (IPCO), 2016.
  Available as arXiv report 1511.07038
  
• Moran Feldman, Ola Svensson, Rico Zenklusen: Online Contention Resolution Schemes.
  Extended abstract in ACM-SIAM Symposium on Discrete Algorithms (SODA), 2016.
  Available as arXiv report 1508.00142
  
• Ola Svensson: Approximating ATSP by Relaxing Connectivity.
  Extended abstract in IEEE Symposium on Foundations of Computer Science (FOCS), 2015.
  Available as arXiv report 1502.02051
  
• Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta, Ola Svensson: No Small Linear Program Approximates Vertex Cover within a Factor 2-epsilon.
  Extended abstract in IEEE Symposium on Foundations of Computer Science (FOCS), 2015.
  Available as arXiv report 1503.00753
• Chidambaram Annamalai, Christos Kalaitzis, and Ola Svensson: Combinatorial Algorithm for Restricted Max-Min Fair Allocation
  Extended abstract in ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015.
  A preliminary version available as arXiv report 1409.0607
• Moran Feldman, Ola Svensson, and Rico Zenklusen: A Simple O(loglog(rank))-Competitive Algorithm for the Matroid Secretary Problem
  Extended abstract in ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015. A preliminary version available as arXiv report 1404.4473
• Hyung-Chan An, Ashkan Norouzi-Fard, and Ola Svensson: Dynamic Facility Location via Exponential Clocks
  Extended abstract in ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015. Invited to TALG special issue.
• Hyung-Chan An, Mohit Singh, and Ola Svensson: LP-Based Algorithms for Capacitated Facility Location
  Extended abstract in the 55th Annual Symposium on Foundations of Computer Science (FOCS), 2014. Invited to SICOMP special issue.
  A preliminary version available as arXiv report 1407.3263
• Hyung-Chan An, Aditya Bhaskara, Chandra Chekuri, Shalmoli Gupta, Vivek Madan, and Ola Svensson: Centrality of Trees for Capacitated k-Center.
  Extended abstract in the 17th Conference on Integer Programming and Combinatorial Optimization (IPCO), 2014.
  Merged paper based on papers by the 1st, 2nd, 6th authors and by the 3rd, 4th, 5th authors.
  A preliminary version available as arXiv report 1304.2983
• Jose Correa, Alberto Marchetti-Spaccamela, Jannik Matuschke, Leen Stougie, Ola Svensson, Víctor Verdugo and José Verschae: Strong LP formulations for scheduling splittable jobs on unrelated machines.
  Extended abstract in the 17th Conference on Integer Programming and Combinatorial Optimization (IPCO), 2014.
• Christos Kalaitzis, Aleksander Madry, Alantha Newman, Lukas Polacek and Ola Svensson: On the Configuration LP for Maximum Budgeted Allocation.
  Extended abstract in the 17th Conference on Integer Programming and Combinatorial Optimization (IPCO), 2014.
• Shi Li, Ola Svensson: Approximating k-median via Pseudo-Approximation.
  Extended abstract in the 45th ACM Symposium on the Theory of Computing (STOC), 2013. Invited to SICOMP special issue.
  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 and Invited Papers

• Ola Svensson: Overview of New Approaches for Approximating TSP.
  Invited paper in 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 2013.
• 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.

---