OS
Ola Svensson
cs.DScs.DMcs.LGcs.CCmath.COcs.AImath.OCstat.MLApproximation algorithmsClustering and facility location
On Valency
published · living versionsW_455wf7yh·v1 · currentpublished
Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms
with Sara Ahmadian, Ashkan Norouzi-Fard, Justin Ward
1 version
Preprints & journals
62 papers in the corpus · 2010–2026A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median2503.10972v2 · Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee et al.2025 · 0 citationsarXiv
A Strong Linear Programming Relaxation for Weighted Tree Augmentation2603.29582v1 · Vincent Cohen-Addad, Marina Drygala, Nathan Klein et al.2026 · 0 citationsarXiv
An Optimal Algorithm for Stochastic Vertex Cover2603.27795v1 · Jan van den Brand, Inge Li G\ortz, Chirag Pabbaraju et al.2026 · 0 citationsarXiv
Accelerating Scientific Research with Gemini: Case Studies and Common Techniques2602.03837v3 · David P. Woodruff, Vincent Cohen-Addad, Lalit Jain et al.2026 · 3 citationsarXiv
Clustering with Label Consistency2512.19654v1 · Diptarka Chakraborty, Hendrik Fichtenberger, Bernhard Haeupler et al.2025 · 0 citationsarXiv
Online Edge Coloring: Sharp Thresholds2507.21560v1 · Joakim Blikstad, Ola Svensson, Radu Vintan et al.2025 · 1 citationarXiv
Nearly Tight Sample Complexity for Matroid Online Contention Resolution2507.09507v1 · Moran Feldman, Ola Svensson, Rico Zenklusen2025 · 1 citationarXiv
The Cost of Consistency: Submodular Maximization with Constant Recourse2412.02492v1 · Paul Dutting, Federico Fusco, Silvio Lattanzi et al.2024 · 0 citationsarXiv
Data-Driven Solution Portfolios2412.00717v1 · Marina Drygala, Silvio Lattanzi, Andreas Maggiori et al.2024 · 0 citationsarXiv
Deterministic Online Bipartite Edge Coloring2408.03661v2 · Joakim Blikstad, Ola Svensson, Radu Vintan et al.2024 · 3 citationsarXiv
Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection2409.17831v1 · Euiwoong Lee, Ola Svensson, Theophile Thiery2024 · 0 citationsarXiv
Fair colorful k-center clustering.35300155 · Jia, Xinrui, Sheth, Kshiteej, Svensson, Ola2024 · 16 citationsMathematical programming. 2022;192(1-2):339-360
Online Edge Coloring is (Nearly) as Easy as Offline2402.18339v1 · Joakim Blikstad, Ola Svensson, Radu Vintan et al.2024 · 8 citationsarXiv
Simple and Asymptotically Optimal Online Bipartite Edge Coloring2311.04574v1 · Joakim Blikstad, Ola Svensson, Radu Vintan et al.2023 · 1 citationarXiv
An Analysis of $D^\alpha$ seeding for $k$-means2310.13474v1 · Etienne Bamas, Sai Ganesh Nagarajan, Ola Svensson2023 · 0 citationsarXiv
The Price of Explainability for Clustering2304.09743v1 · Anupam Gupta, Madhusudhan Reddy Pittu, Ola Svensson et al.2023 · 3 citationsarXiv
Semi-streaming algorithms for submodular matroid intersection.36778060 · Garg, Paritosh, Jordan, Linus, Svensson, Ola2023 · 1 citationMathematical programming. 2023;197(2):967-990
The Exact Bipartite Matching Polytope Has Exponential Extension Complexity2211.09106v1 · Xinrui Jia, Ola Svensson, Weiqiang Yuan2022 · 3 citationsarXiv
A Simple LP-Based Approximation Algorithm for the Matching Augmentation Problem2202.07283v2 · Etienne Bamas, Marina Drygala, Ola Svensson2022 · 7 citationsarXiv
Submodular Maximization Subject to Matroid Intersection on the Fly2204.05154v1 · Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson et al.2022 · 1 citationarXiv
Streaming Submodular Maximization under Matroid Constraints2107.07183v2 · Moran Feldman, Paul Liu, Ashkan Norouzi-Fard et al.2021 · 1 citationarXiv
Flow Time Scheduling and Prefix Beck-Fiala2202.02217v1 · Nikhil Bansal, Lars Rohwedder, Ola Svensson2022 · 10 citationsarXiv
Nearly-Tight and Oblivious Algorithms for Explainable Clustering2106.16147v2 · Buddhima Gamlath, Xinrui Jia, Adam Polak et al.2021 · 6 citationsarXiv
Towards Non-Uniform k-Center with Constant Types of Radii2110.02688v1 · Xinrui Jia, Lars Rohwedder, Kshiteej Sheth et al.2021 · 5 citationsarXiv
A QPTAS for stabbing rectangles2107.06571v1 · Friedrich Eisenbrand, Martina Gallato, Ola Svensson et al.2021 · 0 citationsarXiv
Semi-Streaming Algorithms for Submodular Matroid Intersection2102.04348v1 · Paritosh Garg, Linus Jordan, Ola Svensson2021 · 3 citationsarXiv
Fast and Accurate $k$-means++ via Rejection Sampling2012.11891v1 · Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard et al.2020 · 5 citationsarXiv
Consistent k-Clustering for General Metrics2011.06888v1 · Hendrik Fichtenberger, Silvio Lattanzi, Ashkan Norouzi-Fard et al.2020 · 7 citationsarXiv
Learning Augmented Energy Minimization via Speed Scaling2010.11629v1 · 'Etienne Bamas, Andreas Maggiori, Lars Rohwedder et al.2020 · 23 citationsarXiv
The Primal-Dual method for Learning Augmented Algorithms2010.11632v1 · 'Etienne Bamas, Andreas Maggiori, Ola Svensson2020 · 35 citationsarXiv
A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem1708.04215v4 · Ola Svensson, Jakub Tarnawski, L'aszl'o A. V'egh2017 · 45 citationsarXiv
Fair Colorful k-Center Clustering2007.04059v1 · Xinrui Jia, Kshiteej Sheth, Ola Svensson2020 · 11 citationsIn: Integer Programming and Combinatorial Optimization. IPCO 2020. LNCS, vol 12125. pp 209-222
Robust Algorithms under Adversarial Injections2004.12667v1 · Paritosh Garg, Sagar Kale, Lars Rohwedder et al.2020 · 2 citationsarXiv
The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness2003.13459v1 · Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson et al.2020 · 33 citationsarXiv
Beating Greedy for Stochastic Bipartite Matching1909.12760v2 · Buddhima Gamlath, Sagar Kale, Ola Svensson2019 · 16 citationsarXiv
New Notions and Constructions of Sparsification for Graphs and Hypergraphs1905.01495v1 · Nikhil Bansal, Ola Svensson, Luca Trevisan2019 · 23 citationsarXiv
Online Matching with General Arrivals1904.08255v1 · Buddhima Gamlath, Michael Kapralov, Andreas Maggiori et al.2019 · 54 citationsarXiv
Weighted Matchings via Unweighted Augmentations1811.02760v1 · Buddhima Gamlath, Sagar Kale, Slobodan Mitrovi'c et al.2018 · 44 citationsarXiv
Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering1803.00926v2 · Buddhima Gamlath, Sangxia Huang, Ola Svensson2018 · 7 citationsarXiv
Beyond $1/2$-Approximation for Submodular Maximization on Massive Data Streams1808.01842v1 · Ashkan Norouzi-Fard, Jakub Tarnawski, Slobodan Mitrovi'c et al.2018 · 46 citationsProc. of 35th International Conference on Machine Learning (ICML), 2018, pages 3829-3838
The Matching Problem in General Graphs is in Quasi-NC1704.01929v2 · Ola Svensson, Jakub Tarnawski2017 · 14 citationsProc. of 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2017, pages 696-707
On bounded pitch inequalities for the min-knapsack polytope1801.08850v1 · Yuri Faenza, Igor Malinovi'c, Monaldo Mastrolilli et al.2018 · 3 citationsarXiv
Constant Factor Approximation for ATSP with Two Edge Weights1511.07038v2 · Ola Svensson, Jakub Tarnawski, L'aszl'o A. V'egh2015 · 1 citationProc. of Integer Programming and Combinatorial Optimization: 18th International Conference, IPCO 2016, pages 226-237
Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms1612.07925v2 · Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson et al.2016 · 119 citationsarXivon Valency
A Framework for the Secretary Problem on the Intersection of Matroids1704.02608v1 · Moran Feldman, Ola Svensson, Rico Zenklusen2017 · 10 citationsarXiv
Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios1607.07631v2 · Christos Kalaitzis, Ola Svensson, Jakub Tarnawski2016 · 3 citationsProc. of 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017, pages 2654-2669
Combinatorial Algorithm for Restricted Max-Min Fair Allocation1409.0607v2 · Chidambaram Annamalai, Christos Kalaitzis, Ola Svensson2014 · 38 citationsarXiv
Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits1609.03737v2 · Abbas Bazzi, Samuel Fiorini, Sangxia Huang et al.2016 · 9 citationsarXiv
Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines1511.07826v2 · Nikhil Bansal, Aravind Srinivasan, Ola Svensson2015 · 34 citationsarXiv
No Small Linear Program Approximates Vertex Cover within a Factor $2 - \epsilon$1503.00753v2 · Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta et al.2015 · 3 citationsarXiv
Career total: 173 works. 62 are in this corpus.Showing the 50 most recent.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.