Ola Svensson

STOC Conference 2025 Conference Paper

A (2+ε)-Approximation Algorithm for Metric k-Median

• Vincent Cohen-Addad
• Fabrizio Grandoni 0001
• Euiwoong Lee
• Chris Schwiegelshohn
• Ola Svensson

STOC Conference 2025 Conference Paper

Asymptotically Optimal Hardness for k-Set Packing and k-Matroid Intersection

• Euiwoong Lee
• Ola Svensson
• Theophile Thiery

SODA Conference 2025 Conference Paper

Deterministic Online Bipartite Edge Coloring

• Joakim Blikstad
• Ola Svensson
• Radu Vintan
• David Wajc

FOCS Conference 2025 Conference Paper

Online Edge Coloring: Sharp Thresholds

• Joakim Blikstad
• Ola Svensson
• Radu Vintan
• David Wajc

Vizing’s theorem guarantees that every graph with maximum degree $\Delta$ admits an edge coloring using $\Delta+1$ colors. In online settings-where edges arrive one at a time and must be colored immediately-a simple greedy algorithm uses at most $2 \Delta-1$ colors. Over thirty years ago, Bar-Noy, Motwani, and Naor [IPL’92] proved that this guarantee is optimal among deterministic algorithms when $\Delta=O(\log n)$, and among randomized algorithms when $\Delta=O(\sqrt{\log n})$. While deterministic improvements seemed out of reach, they conjectured that for graphs with $\Delta=\omega(\log n)$, randomized algorithms can achieve $(1+o(1)) \Delta$ edge coloring. This conjecture was recently resolved in the affirmative: a $(1+o(1)) \Delta$ coloring is achievable online using randomization for all graphs with $\Delta=\omega(\log n)$ [BSVW STOC’24]. Our results go further, uncovering two findings not predicted by the original conjecture. First, we give a deterministic online algorithm achieving $(1+o(1)) \Delta$-colorings for all $\Delta=\omega(\log n)$. Second, we give a randomized algorithm achieving $(1+o(1)) \Delta$ colorings already when $\Delta=\omega(\sqrt{\log n})$. Our results establish sharp thresholds for when greedy can be surpassed, and nearoptimal guarantees can be achieved - matching the impossibility results of [BNMN IPL’92], both deterministically and randomly.

STOC Conference 2025 Conference Paper

The Cost of Consistency: Submodular Maximization with Constant Recourse

• Paul Dütting
• Federico Fusco 0001
• Silvio Lattanzi
• Ashkan Norouzi-Fard
• Ola Svensson
• Morteza Zadimoghaddam

ICML Conference 2024 Conference Paper

Analyzing Dα seeding for k-means

• Étienne Bamas
• Sai Ganesh Nagarajan
• Ola Svensson

One of the most popular clustering algorithms is the celebrated $D^\alpha$ seeding algorithm (also know as $k$-means++ when $\alpha=2$) by Arthur and Vassilvitskii (2007), who showed that it guarantees in expectation an $O(2^{2\alpha}\cdot \log k)$-approximate solution to the ($k$, $\alpha$)-clustering cost (where distances are raised to the power $\alpha$) for any $\alpha\ge 1$. More recently, Balcan, Dick, and White (2018) observed experimentally that using $D^\alpha$ seeding with $\alpha>2$ can lead to a better solution with respect to the standard $k$-means objective (i. e. the $(k, 2)$-clustering cost). In this paper, we provide a rigorous understanding of this phenomenon. For any $\alpha>2$, we show that $D^\alpha$ seeding guarantees in expectation an approximation factor of \begin{equation*} O_\alpha \left(\left(\frac{\sigma_{\textrm{max}}}{\sigma_{\textrm{min}}}\right)^{2-4/\alpha}\cdot (g_\alpha \cdot \min \lbrace\ell, \log k\rbrace)^{2/\alpha}\right) \end{equation*} with respect to the standard $k$-means cost of any underlying clustering; where $g_\alpha$ is a parameter capturing the concentration of the points in each cluster, $\sigma_{\textrm{max}}$ and $\sigma_{\textrm{min}}$ are the maximum and minimum standard deviation of the clusters around their center, and $\ell$ is the number of distinct mixing weights in the underlying clustering (after rounding them to the nearest power of $2$). For instance, if the underlying clustering is defined by a mixture of $k$ Gaussian distributions with equal cluster variance (up to a constant-factor), then our result implies that: (1) if there are a constant number of mixing weights, any constant $\alpha>2$ yields a constant-factor approximation; (2) if the mixing weights are arbitrary, any constant $\alpha>2$ yields an $O\left(\log^{2/\alpha}k\right)$-approximation, and $\alpha=\Theta(\log\log k)$ yields an $O(\log\log k)^3$-approximation. We complement these results by some lower bounds showing that the dependency on $g_\alpha$ and $\sigma_{\textrm{max}}/\sigma_{\textrm{min}}$ is tight. Finally, we provide an experimental validation of the effects of the aforementioned parameters when using $D^\alpha$ seeding.

STOC Conference 2024 Conference Paper

Online Edge Coloring Is (Nearly) as Easy as Offline

• Joakim Blikstad
• Ola Svensson
• Radu Vintan
• David Wajc

The classic theorem of Vizing (Diskret. Analiz.’64) asserts that any graph of maximum degree Δ can be edge colored (offline) using no more than Δ+1 colors (with Δ being a trivial lower bound). In the online setting, Bar-Noy, Motwani and Naor (IPL’92) conjectured that a (1+ o (1))Δ-edge-coloring can be computed online in n -vertex graphs of maximum degree Δ=ω(log n ). Numerous algorithms made progress on this question, using a higher number of colors or assuming restricted arrival models, such as random-order edge arrivals or vertex arrivals (e.g., AGKM FOCS’03, BMM SODA’10, CPW FOCS’19, BGW SODA’21, KLSST STOC’22). In this work, we resolve this longstanding conjecture in the affirmative in the most general setting of adversarial edge arrivals. We further generalize this result to obtain online counterparts of the list edge coloring result of Kahn (J. Comb. Theory. A’96) and of the recent “local” edge coloring result of Christiansen (STOC’23).

ICML Conference 2023 Conference Paper

Speeding Up Bellman Ford via Minimum Violation Permutations

• Silvio Lattanzi
• Ola Svensson
• Sergei Vassilvitskii

The Bellman-Ford algorithm is a basic primitive for computing single source shortest paths in graphs with negative weight edges. Its running time is governed by the order the algorithm examines vertices for iterative updates on the value of their shortest path. In this work we study this problem through the lens of ’Algorithms with predictions, ’ and show how to leverage auxiliary information from similar instances to improve the running time. We do this by identifying the key problem of Minimum Violation Permutations, and give algorithms with strong approximation guarantees as well as formal lower bounds. We complement the theoretical analysis with an empirical evaluation, showing that this approach can lead to a significant speed up in practice.

SODA Conference 2023 Conference Paper

The Exact Bipartite Matching Polytope Has Exponential Extension Complexity

• Xinrui Jia 0001
• Ola Svensson
• Weiqiang Yuan 0002

Given a graph with edges colored red or blue and an integer k, the exact perfect matching problem asks if there exists a perfect matching with exactly k red edges. There exists a randomized polylogarithmic-time parallel algorithm to solve this problem, dating back to the eighties, but no deterministic polynomial-time algorithm is known, even for bipartite graphs. In this paper we show that there is no sub-exponential sized linear program that can describe the convex hull of exact matchings in bipartite graphs. In fact, we prove something stronger, that there is no sub-exponential sized linear program to describe the convex hull of perfect matchings with an odd number of red edges.

FOCS Conference 2023 Conference Paper

The Price of Explainability for Clustering

• Anupam Gupta 0001
• Madhusudhan Reddy Pittu
• Ola Svensson
• Rachel Yuan

Given a set of points in d-dimensional space, an explainable clustering is one where the clusters are specified by a tree of axis-aligned threshold cuts. Dasgupta et al. (ICML 2020) posed the question of the price of explainability: the worst-case ratio between the cost of the best explainable clusterings to that of the best clusterings. We show that the price of explainability for k medians is at most $1+H_{k-1}$; in fact, we show that the popular Random Thresholds algorithm has exactly this price of explainability, matching the known lower bound constructions. We complement our tight analysis of this particular algorithm by constructing instances where the price of explainability (using any algorithm) is at least $(1-o(1)) \ln k$, showing that our result is best possible, up to lower-order terms. We also improve the price of explainability for the k-means problem to $O(k \ln \ln k)$ from the previous $O(k \ln k)$, considerably closing the gap to the lower bounds of $\Omega(k)$. Finally, we study the algorithmic question of finding the best explainable clustering: We show that explainable k medians and k-means cannot be approximated better than $O(\ln k)$, under standard complexity-theoretic conjectures. This essentially settles the approximability of explainable k-medians and leaves open the intriguing possibility to get significantly better approximation algorithms for k-means than its price of explainability.

STOC Conference 2022 Conference Paper

Flow time scheduling and prefix Beck-Fiala

• Nikhil Bansal 0001
• Lars Rohwedder
• Ola Svensson

We relate discrepancy theory with the classic scheduling problems of minimizing max flow time and total flow time on unrelated machines. Specifically, we give a general reduction that allows us to transfer discrepancy bounds in the prefix Beck-Fiala (bounded ℓ 1 -norm) setting to bounds on the flow time of an optimal schedule. Combining our reduction with a deep result proved by Banaszczyk via convex geometry, give guarantees of O (√log n ) and O (√log n log P ) for max flow time and total flow time, respectively, improving upon the previous best guarantees of O (log n ) and O (log n log P ). Apart from the improved guarantees, the reduction motivates seemingly easy versions of prefix discrepancy questions: any constant bound on prefix Beck-Fiala where vectors have sparsity two (sparsity one being trivial) would already yield tight guarantees for both max flow time and total flow time. While known techniques solve this case when the entries take values in {−1,0,1}, we show that they are unlikely to transfer to the more general 2-sparse case of bounded ℓ 1 -norm.

SODA Conference 2021 Conference Paper

Consistent k-Clustering for General Metrics

• Hendrik Fichtenberger
• Silvio Lattanzi
• Ashkan Norouzi-Fard
• Ola Svensson

Given a stream of points in a metric space, is it possible to maintain a constant approximate clustering by changing the cluster centers only a small number of times during the entire execution of the algorithm? This question received attention in recent years in the machine learning literature and, before our work, the best known algorithm performs Õ ( k 2 ) center swaps (the Õ (·) notation hides polylogarithmic factors in the number of points n and the aspect ratio Δ of the input instance). This is a quadratic increase compared to the offline case — the whole stream is known in advance and one is interested in keeping a constant approximation at any point in time — for which Õ ( k ) swaps are known to be sufficient and simple examples show that Ω( k log( n Δ)) swaps are necessary. We close this gap by developing an algorithm that, perhaps surprisingly, matches the guarantees in the offline setting. Specifically, we show how to maintain a constant-factor approximation for the k -median problem by performing an optimal (up to polylogarithimic factors) number Õ ( k ) of center swaps. To obtain our result we leverage new structural properties of k -median clustering that may be of independent interest.

NeurIPS Conference 2021 Conference Paper

Nearly-Tight and Oblivious Algorithms for Explainable Clustering

• Buddhima Gamlath
• Xinrui Jia
• Adam Polak
• Ola Svensson

We study the problem of explainable clustering in the setting first formalized by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020). A $k$-clustering is said to be explainable if it is given by a decision tree where each internal node splits data points with a threshold cut in a single dimension (feature), and each of the $k$ leaves corresponds to a cluster. We give an algorithm that outputs an explainable clustering that loses at most a factor of $O(\log^2 k)$ compared to an optimal (not necessarily explainable) clustering for the $k$-medians objective, and a factor of $O(k \log^2 k)$ for the $k$-means objective. This improves over the previous best upper bounds of $O(k)$ and $O(k^2)$, respectively, and nearly matches the previous $\Omega(\log k)$ lower bound for $k$-medians and our new $\Omega(k)$ lower bound for $k$-means. The algorithm is remarkably simple. In particular, given an initial not necessarily explainable clustering in $\mathbb{R}^d$, it is oblivious to the data points and runs in time $O(dk \log^2 k)$, independent of the number of data points $n$. Our upper and lower bounds also generalize to objectives given by higher $\ell_p$-norms.

NeurIPS Conference 2021 Conference Paper

Parallel and Efficient Hierarchical k-Median Clustering

• Vincent Cohen-Addad
• Silvio Lattanzi
• Ashkan Norouzi-Fard
• Christian Sohler
• Ola Svensson

As a fundamental unsupervised learning task, hierarchical clustering has been extensively studied in the past decade. In particular, standard metric formulations as hierarchical $k$-center, $k$-means, and $k$-median received a lot of attention and the problems have been studied extensively in different models of computation. Despite all this interest, not many efficient parallel algorithms are known for these problems. In this paper we introduce a new parallel algorithm for the Euclidean hierarchical $k$-median problem that, when using machines with memory $s$ (for $s\in \Omega(\log^2 (n+\Delta+d))$), outputs a hierarchical clustering such that for every fixed value of $k$ the cost of the solution is at most an $O(\min\{d, \log n\} \log \Delta)$ factor larger in expectation than that of an optimal solution. Furthermore, we also get that for all $k$ simultanuously the cost of the solution is at most an $O(\min\{d, \log n\} \log \Delta \log (\Delta d n))$ factor bigger that the corresponding optimal solution. The algorithm requires in $O\left(\log_{s} (nd\log(n+\Delta))\right)$ rounds. Here $d$ is the dimension of the data set and $\Delta$ is the ratio between the maximum and minimum distance of two points in the input dataset. To the best of our knowledge, this is the first \emph{parallel} algorithm for the hierarchical $k$-median problem with theoretical guarantees. We further complement our theoretical results with an empirical study of our algorithm that shows its effectiveness in practice.

NeurIPS Conference 2020 Conference Paper

Fast and Accurate $k$-means++ via Rejection Sampling

• Vincent Cohen-Addad
• Silvio Lattanzi
• Ashkan Norouzi-Fard
• Christian Sohler
• Ola Svensson

$k$-means++ \cite{arthur2007k} is a widely used clustering algorithm that is easy to implement, has nice theoretical guarantees and strong empirical performance. Despite its wide adoption, $k$-means++ sometimes suffers from being slow on large data-sets so a natural question has been to obtain more efficient algorithms with similar guarantees. In this paper, we present such a near linear time algorithm for $k$-means++ seeding. Interestingly our algorithm obtains the same theoretical guarantees as $k$-means++ and significantly improves earlier results on fast $k$-means++ seeding. Moreover, we show empirically that our algorithm is significantly faster than $k$-means++ and obtains solutions of equivalent quality.

NeurIPS Conference 2020 Conference Paper

Learning Augmented Energy Minimization via Speed Scaling

• Etienne Bamas
• Andreas Maggiori
• Lars Rohwedder
• Ola Svensson

As power management has become a primary concern in modern data centers, computing resources are being scaled dynamically to minimize energy consumption. We initiate the study of a variant of the classic online speed scaling problem, in which machine learning predictions about the future can be integrated naturally. Inspired by recent work on learning-augmented online algorithms, we propose an algorithm which incorporates predictions in a black-box manner and outperforms any online algorithm if the accuracy is high, yet maintains provable guarantees if the prediction is very inaccurate. We provide both theoretical and experimental evidence to support our claims.

STOC Conference 2020 Conference Paper

The one-way communication complexity of submodular maximization with applications to streaming and robustness

• Moran Feldman
• Ashkan Norouzi-Fard
• Ola Svensson
• Rico Zenklusen

We consider the classical problem of maximizing a monotone submodular function subject to a cardinality constraint, which, due to its numerous applications, has recently been studied in various computational models. We consider a clean multi-player model that lies between the offline and streaming model, and study it under the aspect of one-way communication complexity. Our model captures the streaming setting (by considering a large number of players), and, in addition, two player approximation results for it translate into the robust setting. We present tight one-way communication complexity results for our model, which, due to the above-mentioned connections, have multiple implications in the data stream and robust setting.

NeurIPS Conference 2020 Conference Paper

The Primal-Dual method for Learning Augmented Algorithms

• Etienne Bamas
• Andreas Maggiori
• Ola Svensson

The extension of classical online algorithms when provided with predictions is a new and active research area. In this paper, we extend the primal-dual method for online algorithms in order to incorporate predictions that advise the online algorithm about the next action to take. We use this framework to obtain novel algorithms for a variety of online covering problems. We compare our algorithms to the cost of the true and predicted offline optimal solutions and show that these algorithms outperform any online algorithm when the prediction is accurate while maintaining good guarantees when the prediction is misleading.

SODA Conference 2019 Conference Paper

Beating Greedy for Stochastic Bipartite Matching

• Buddhima Gamlath
• Sagar Sudhir Kale
• Ola Svensson

We consider the maximum bipartite matching problem in stochastic settings, namely the query-commit and price-of-information models. In the query-commit model, an edge e independently exists with probability p e. We can query whether an edge exists or not, but if it does exist, then we have to take it into our solution. In the unweighted case, one can query edges in the order given by the classical online algorithm of Karp, Vazirani, and Vazirani [20] to get a (1 – 1/ e )-approximation. In contrast, the previously best known algorithm in the weighted case is the (1/2)-approximation achieved by the greedy algorithm that sorts the edges according to their weights and queries in that order. Improving upon the basic greedy, we give a (1 – 1/e)-approximation algorithm in the weighted query-commit model. We use a linear program (LP) to upper bound the optimum achieved by any strategy. The proposed LP admits several structural properties that play a crucial role in the design and analysis of our algorithm. We also extend these techniques to get a (1 – 1/ e )-approximation algorithm for maximum bipartite matching in the price-of-information model introduced by Singla [25], who also used the basic greedy algorithm to give a (1/2)-approximation.

FOCS Conference 2019 Conference Paper

New Notions and Constructions of Sparsification for Graphs and Hypergraphs

• Nikhil Bansal 0001
• Ola Svensson
• Luca Trevisan 0001

A sparsifier of a graph G (Benczúr and Karger; Spielman and Teng) is a sparse weighted subgraph G that approximately retains the same cut structure of G. For general graphs, non-trivial sparsification is possible only by using weighted graphs in which different edges have different weights. Even for graphs that admit unweighted sparsifiers (that is, sparsifiers in which all the edge weights are equal to the same scaling factor), there are no known polynomial time algorithms that find such unweighted sparsifiers. We study a weaker notion of sparsification suggested by Oveis Gharan, in which the number of cut edges in each cut (S, S) is not approximated within a multiplicative factor (1+ε), but is, instead, approximated up to an additive term bounded by ε times d⋅|S| + vol (S), where d is the average degree of the graph and vol (S) is the sum of the degrees of the vertices in S. We provide a probabilistic polynomial time construction of such sparsifiers for every graph, and our sparsifiers have a near-optimal number of edges O(ε^-2 npolylog (1/ε)). We also provide a deterministic polynomial time construction that constructs sparsifiers with a weaker property having the optimal number of edges O(ε^-2 n). Our constructions also satisfy a spectral version of the “additive sparsification'' property. Notions of sparsification have also been studied for hypergraphs. Our construction of “additive sparsifiers'' with O_ε (n) edges also works for hypergraphs, and provides the first non-trivial notion of sparsification for hypergraphs achievable with O(n) hyperedges when ε and the rank r of the hyperedges are constant. Finally, we provide a new construction of spectral hypergraph sparsifiers, according to the standard definition, with poly (ε^-1, r) n log n hyperedges, improving over the previous spectral construction (Soma and Yoshida) that used Õ(n^3) hyperedges even for constant r and ε.

FOCS Conference 2019 Conference Paper

Online Matching with General Arrivals

• Buddhima Gamlath
• Michael Kapralov
• Andreas Maggiori
• Ola Svensson
• David Wajc

The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertices arriving only on one side, and presented optimal deterministic and randomized algorithms for this setting. In comparison, more general arrival models, such as edge arrivals and general vertex arrivals, have proven more challenging and positive results are known only for various relaxations of the problem. In particular, even the basic question of whether randomization allows one to beat the trivially-optimal deterministic competitive ratio of 1/2 for either of these models was open. In this paper, we resolve this question for both these natural arrival models, and show the following. 1) For edge arrivals, randomization does not help - no randomized algorithm is better than 1/2 competitive. 2)For general vertex arrivals, randomization helps - there exists a randomized (1/2+Ω(1)) -competitive online matching algorithm.

STOC Conference 2018 Conference Paper

A constant-factor approximation algorithm for the asymmetric traveling salesman problem

• Ola Svensson
• Jakub Tarnawski
• László A. Végh

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation.

SODA Conference 2018 Conference Paper

A Framework for the Secretary Problem on the Intersection of Matroids

• Moran Feldman
• Ola Svensson
• Rico Zenklusen

The secretary problem became one of the most prominent online selection problems due to its numerous applications in online mechanism design. The task is to select a maximum weight subset of elements subject to given constraints, where elements arrive one-by-one in random order, revealing a weight upon arrival. The decision whether to select an element has to be taken immediately after its arrival. The different applications that map to the secretary problem ask for different constraint families to be handled. The most prominent ones are matroid constraints, which both capture many relevant settings and admit strongly competitive secretary algorithms. However, dealing with more involved constraints proved to be much more difficult, and strong algorithms are known only for a few specific settings. In this paper, we present a general framework for dealing with the secretary problem over the intersection of several matroids. This framework allows us to combine and exploit the large set of matroid secretary algorithms known in the literature. As one consequence, we get constant-competitive secretary algorithms over the intersection of any constant number of matroids whose corresponding (single-)matroid secretary problems are currently known to have a constant-competitive algorithm. Moreover, we show that our results extend to submodular objectives.

ICML Conference 2018 Conference Paper

Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams

• Ashkan Norouzi-Fard
• Jakub Tarnawski
• Slobodan Mitrovic
• Amir Zandieh
• Aida Mousavifar
• Ola Svensson

Many tasks in machine learning and data mining, such as data diversification, non-parametric learning, kernel machines, clustering etc. , require extracting a small but representative summary from a massive dataset. Often, such problems can be posed as maximizing a submodular set function subject to a cardinality constraint. We consider this question in the streaming setting, where elements arrive over time at a fast pace and thus we need to design an efficient, low-memory algorithm. One such method, proposed by Badanidiyuru et al. (2014), always finds a 0. 5-approximate solution. Can this approximation factor be improved? We answer this question affirmatively by designing a new algorithm Salsa for streaming submodular maximization. It is the first low-memory, singlepass algorithm that improves the factor 0. 5, under the natural assumption that elements arrive in a random order. We also show that this assumption is necessary, i. e. , that there is no such algorithm with better than 0. 5-approximation when elements arrive in arbitrary order. Our experiments demonstrate that Salsa significantly outperforms the state of the art in applications related to exemplar-based clustering, social graph analysis, and recommender systems.

FOCS Conference 2017 Conference Paper

Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms

• Sara Ahmadian
• Ashkan Norouzi-Fard
• Ola Svensson
• Justin Ward

Clustering is a classic topic in optimization with k-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best known algorithm for k-means with a provable guarantee is a simple local search heuristic yielding an approximation guarantee of 9 + ε, a ratio that is known to be tight with respect to such methods. We overcome this barrier by presenting a new primal-dual approach that allows us to (1) exploit the geometric structure of k-means and (2) to satisfy the hard constraint that at most k clusters are selected without deteriorating the approximation guarantee. Our main result is a 6. 357-approximation algorithm with respect to the standard LP relaxation. Our techniques are quite general and we also show improved guarantees for the general version of k-means where the underlying metric is not required to be Euclidean and for k-median in Euclidean metrics.

SODA Conference 2017 Conference Paper

Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

• Abbas Bazzi
• Samuel Fiorini
• Sangxia Huang
• Ola Svensson

Initially developed for the min-knapsack problem, the knapsack cover inequalities are used in the current best relaxations for numerous combinatorial optimization problems of covering type. In spite of their widespread use, these inequalities yield linear programming (LP) relaxations of exponential size, over which it is not known how to optimize exactly in polynomial time. In this paper we address this issue and obtain LP relaxations of quasi-polynomial size that are at least as strong as that given by the knapsack cover inequalities. For the min-knapsack cover problem, our main result can be stated formally as follows: for any ∊ > 0, there is a (1/∊) O (1) n O (log n ) -size LP relaxation with an integrality gap of at most 2 + ∊, where n is the number of items. Prior to this work, there was no known relaxation of subexponential size with a constant upper bound on the integrality gap. Our construction is inspired by a connection between extended formulations and monotone circuit complexity via Karchmer-Wigderson games. In particular, our LP is based on O (log 2 n )-depth monotone circuits with fan-in 2 for evaluating weighted threshold functions with n inputs, as constructed by Beimel and Weinreb. We believe that a further understanding of this connection may lead to more positive results complementing the numerous lower bounds recently proved for extended formulations.

FOCS Conference 2017 Conference Paper

The Matching Problem in General Graphs Is in Quasi-NC

• Ola Svensson
• Jakub Tarnawski

We show that the perfect matching problem in general graphs is in Quasi-NC. That is, we give a deterministic parallel algorithm which runs in O(log 3 n) time on n O(log2 n) processors. The result is obtained by a derandomization of the Isolation Lemma for perfect matchings, which was introduced in the classic paper by Mulmuley, Vazirani and Vazirani [1987] to obtain a Randomized NC algorithm. Our proof extends the framework of Fenner, Gurjar and Thierauf [2016], who proved the analogous result in the special case of bipartite graphs. Compared to that setting, several new ingredients are needed due to the significantly more complex structure of perfect matchings in general graphs. In particular, our proof heavily relies on the laminar structure of the faces of the perfect matching polytope.

SODA Conference 2017 Conference Paper

Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios

• Christos Kalaitzis
• Ola Svensson
• Jakub Tarnawski

We consider the classic problem of scheduling jobs on unrelated machines so as to minimize the weighted sum of completion times. Recently, for a small constant ∊ > 0, Bansal et al. gave a (3/2 – ∊)-approximation algorithm improving upon the “natural” barrier of 3/2 which follows from independent randomized rounding. In simplified terms, their result is obtained by an enhancement of independent randomized rounding via strong negative correlation properties. In this work, we take a different approach and propose to use the same elegant rounding scheme for the weighted completion time objective as devised by Shmoys and Tardos for optimizing a linear function subject to makespan constraints. Our main result is a 1. 21-approximation algorithm for the natural special case where the weight of a job is proportional to its processing time (specifically, all jobs have the same Smith ratio), which expresses the notion that each unit of work has the same weight. In addition, as a direct consequence of the rounding, our algorithm also achieves a bi-criteria 2-approximation for the makespan objective. Our technical contribution is a tight analysis of the expected cost of the solution compared to the one given by the Configuration-LP relaxation - we reduce this task to that of understanding certain worst-case instances which are simple to analyze.

STOC Conference 2016 Conference Paper

Lift-and-round to improve weighted completion time on unrelated machines

• Nikhil Bansal 0001
• Aravind Srinivasan
• Ola Svensson

We consider the problem of scheduling jobs on unrelated machines so as to minimize the sum of weighted completion times. Our main result is a (3/2-c)-approximation algorithm for some fixed c>0, improving upon the long-standing bound of 3/2. To do this, we first introduce a new lift-and-project based SDP relaxation for the problem. This is necessary as the previous convex programming relaxations have an integrality gap of 3/2. Second, we give a new general bipartite-rounding procedure that produces an assignment with certain strong negative correlation properties.

NeurIPS Conference 2016 Conference Paper

Linear Relaxations for Finding Diverse Elements in Metric Spaces

• Aditya Bhaskara
• Mehrdad Ghadiri
• Vahab Mirrokni
• Ola Svensson

Choosing a diverse subset of a large collection of points in a metric space is a fundamental problem, with applications in feature selection, recommender systems, web search, data summarization, etc. Various notions of diversity have been proposed, tailored to different applications. The general algorithmic goal is to find a subset of points that maximize diversity, while obeying a cardinality (or more generally, matroid) constraint. The goal of this paper is to develop a novel linear programming (LP) framework that allows us to design approximation algorithms for such problems. We study an objective known as {\em sum-min} diversity, which is known to be effective in many applications, and give the first constant factor approximation algorithm. Our LP framework allows us to easily incorporate additional constraints, as well as secondary objectives. We also prove a hardness result for two natural diversity objectives, under the so-called {\em planted clique} assumption. Finally, we study the empirical performance of our algorithm on several standard datasets. We first study the approximation quality of the algorithm by comparing with the LP objective. Then, we compare the quality of the solutions produced by our method with other popular diversity maximization algorithms.

SODA Conference 2016 Conference Paper

Online Contention Resolution Schemes

• Moran Feldman
• Ola Svensson
• Rico Zenklusen

We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution schemes, a technique initially introduced in the context of submodular function maximization. Our rounding technique, which we call online contention resolution schemes (OCRSs), is applicable to many online selection problems, including Bayesian online selection, oblivious posted pricing mechanisms, and stochastic probing models. It allows for handling a wide set of constraints, and shares many strong properties of offline contention resolution schemes. In particular, OCRSs for different constraint families can be combined to obtain an OCRS for their intersection. Moreover, we can approximately maximize submodular functions in the online settings we consider. We, thus, get a broadly applicable framework for several online selection problems, which improves on previous approaches in terms of the types of constraints that can be handled, the objective functions that can be dealt with, and the assumptions on the strength of the adversary. Furthermore, we resolve two open problems from the literature; namely, we present the first constant-factor constrained oblivious posted price mechanism for matroid constraints, and the first constant-factor algorithm for weighted stochastic probing with deadlines.

SODA Conference 2015 Conference Paper

A Simple O (log log(rank))-Competitive Algorithm for the Matroid Secretary Problem

• Moran Feldman
• Ola Svensson
• Rico Zenklusen

Only recently progress has been made in obtaining o (log(rank))-competitive algorithms for the matroid secretary problem. More precisely, Chakraborty and Lachish (2012) presented a -competitive procedure, and Lachish (2014) recently presented a O (log log(rank))-competitive algorithm. Both algorithms are involved with complex analyses. Using different tools, we present a considerably simpler O (log log(rank))-competitive algorithm. Our algorithm can be interpreted as a distribution over a simple type of matroid secretary algorithms which are easy to analyze. We are also able to vastly improve on the hidden constant in the competitive ratio.

FOCS Conference 2015 Conference Paper

Approximating ATSP by Relaxing Connectivity

• Ola Svensson

The standard LP relaxation of the asymmetric traveling salesman problem has been conjectured to have a constant integrality gap in the metric case. We prove this conjecture when restricted to shortest path metrics of node-weighted digraphs. Our arguments are constructive and give a constant factor approximation algorithm for these metrics. We remark that the considered case is more general than the directed analog of the special case of the symmetric traveling salesman problem for which there were recent improvements on Christofides' algorithm. The main idea of our approach is to first consider an easier problem obtained by significantly relaxing the general connectivity requirements into local connectivity conditions. For this relaxed problem, it is quite easy to give an algorithm with a guarantee of 3 on node-weighted shortest path metrics. More surprisingly, we then show that any algorithm (irrespective of the metric) for the relaxed problem can be turned into an algorithm for the asymmetric traveling salesman problem by only losing a small constant factor in the performance guarantee. This leaves open the intriguing task of designing a "good" algorithm for the relaxed problem on general metrics.

SODA Conference 2015 Conference Paper

Combinatorial Algorithm for Restricted Max-Min Fair Allocation

• Chidambaram Annamalai 0001
• Christos Kalaitzis
• Ola Svensson

We study the basic allocation problem of assigning resources to players so as to maximize fairness. This is one of the few natural problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, a certain configuration-LP can be used to estimate the value of the optimal allocation to within a factor of 4 + ε. In contrast, however, the best known approximation algorithm for the problem has an unspecified large constant guarantee. In this paper we significantly narrow this gap by giving a 13-approximation algorithm for the problem. Our approach develops a local search technique introduced by Haxell [11] for hypergraph matchings, and later used in this context by Asadpour, Feige, and Saberi [1]. For our local search procedure to terminate in polynomial time, we introduce several new ideas such as lazy updates and greedy players. Besides the improved approximation guarantee, the highlight of our approach is that it is purely combinatorial and uses the configuration-LP only in the analysis.

SODA Conference 2015 Conference Paper

Dynamic Facility Location via Exponential Clocks

• Hyung-Chan An
• Ashkan Norouzi-Fard
• Ola Svensson

The dynamic facility location problem is a generalization of the classic facility location problem proposed by Eisenstat, Mathieu, and Schabanel to model the dynamics of evolving social/infrastructure networks. The generalization lies in that the distance metric between clients and facilities changes over time. This leads to a trade-off between optimizing the classic objective function and the “stability” of the solution: there is a switching cost charged every time a client changes the facility to which it is connected. While the standard linear program (LP) relaxation for the classic problem naturally extends to this problem, traditional LP-rounding techniques do not, as they are often sensitive to small changes in the metric resulting in frequent switches. We present a new LP-rounding algorithm for facility location problems, which yields the first constant approximation algorithm for the dynamic facility location problem. Our algorithm installs competing exponential clocks on the clients and facilities, and connect every client by the path that repeatedly follows the smallest clock in the neighborhood. The use of exponential clocks gives rise to several properties that distinguish our approach from previous LP-roundings for facility location problems. In particular, we use no clustering and we allow clients to connect through paths of arbitrary lengths. In fact, the clustering-free nature of our algorithm is crucial for applying our LP-rounding approach to the dynamic problem.

FOCS Conference 2015 Conference Paper

No Small Linear Program Approximates Vertex Cover within a Factor 2 - e

• Abbas Bazzi
• Samuel Fiorini
• Sebastian Pokutta
• Ola Svensson

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [30], [31] proved that the problem is NP-hard to approximate within a factor 2 - ε, assuming the Unique Games Conjecture (UGC). This is tight because the problem has an easy 2-approximation algorithm. Without resorting to the UGC, the best in approximability result for the problem is due to Dinur and Safra [16], [17]: vertex cover is NP-hard to approximate within a factor 1. 3606. We prove the following unconditional result about linear programming (LP) relaxations of the problem: every LP relaxation that approximates vertex cover within a factor of 2 - ε has super-polynomially many inequalities. As a direct consequence of our methods, we also establish that LP relaxations (as well as SDP relaxations) that approximate the independent set problem within any constant factor have super-polynomially many inequalities.

FOCS Conference 2014 Conference Paper

LP-Based Algorithms for Capacitated Facility Location

• Hyung-Chan An
• Mohit Singh
• Ola Svensson

Linear programming has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic methodologies, such as LP-rounding and primal-dual method, have been applied to and evolved from algorithms for this problem. Unfortunately, this collection of powerful algorithmic techniques had not yet been applicable to the more general capacitated facility location problem. In fact, all of the known algorithms with good performance guarantees were based on a single technique, local search, and no linear programming relaxation was known to efficiently approximate the problem. In this paper, we present a linear programming relaxation with constant integrality gap for capacitated facility location. We demonstrate that the fundamental theories of multi-commodity flows and matchings provide key insights that lead to the strong relaxation. Our algorithmic proof of integrality gap is obtained by finally accessing the rich toolbox of LP-based methodologies: we present a constant factor approximation algorithm based on LP-rounding.

STOC Conference 2013 Conference Paper

Approximating k-median via pseudo-approximation

• Shi Li 0001
• Ola Svensson

We present a novel approximation algorithm for k-median that achieves an approximation guarantee of 1+√3+ε, improving upon the decade-old ratio of 3+ε. Our approach is based on two components, each of which, we believe, is of independent interest. First, we show that in order to give an α-approximation algorithm for k-median, it is sufficient to give a pseudo-approximation algorithm that finds an α-approximate solution by opening k+O(1) facilities. This is a rather surprising result as there exist instances for which opening k+1 facilities may lead to a significant smaller cost than if only k facilities were opened.

TCS Journal 2013 Journal Article

Single machine scheduling with scenarios

• Monaldo Mastrolilli
• Nikolaus Mutsanas
• Ola Svensson

In the field of robust optimization, the goal is to provide solutions to combinatorial problems that hedge against variations of the numerical parameters. This constitutes an effort to design algorithms that are applicable in the presence of uncertainty in the definition of the instance. We study the single machine scheduling problem with the objective of minimizing the weighted sum of completion times. We model uncertainty by replacing the vector of numerical values in the description of the instance by a set of possible vectors, called scenarios. The goal is to find a schedule of minimum value in the worst-case scenario. We first show that the general problem cannot be approximated within O ( log 1 − ε n ) for any ε > 0, unless NP has quasi-polynomial algorithms. We then study more tractable special cases and obtain a linear program (LP)-based 2 -approximation algorithm for the unweighted case. We show that our analysis is tight by providing a matching lower bound on the integrality gap of the LP. Moreover, we prove that the unweighted version is NP-hard to approximate within a factor less than 6 / 5. We conclude by presenting a polynomial-time algorithm based on dynamic programming for the case when the number of scenarios and the values of the instance are bounded by some constant.

FOCS Conference 2011 Conference Paper

Approximating Graphic TSP by Matchings

• Tobias Mömke
• Ola Svensson

We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a decreased cost. For the TSP on graphic metrics (graph-TSP), the approach yields a 1. 461-approximation algorithm with respect to the Held-Karp lower bound. For graph-TSP restricted to a class of graphs that contains degree three bounded and claw-free graphs, we show that the integrality gap of the Held-Karp relaxation matches the conjectured ratio 4/3. The framework allows for generalizations in a natural way and also leads to a 1. 586-approximation algorithm for the traveling salesman path problem on graphic metrics where the start and end vertices are prespecified.

STOC Conference 2011 Conference Paper

Santa Claus schedules jobs on unrelated machines

• Ola Svensson

STOC Conference 2010 Conference Paper

Conditional hardness of precedence constrained scheduling on identical machines

• Ola Svensson

Already in 1966, Graham showed that a simple procedure called list scheduling yields a 2-approximation algorithm for the central problem of scheduling precedence constrained jobs on identical machines to minimize makespan. Till this date it has remained the best algorithm and whether it can or cannot be improved has become a major open problem in scheduling theory.

FOCS Conference 2008 Conference Paper

(Acyclic) JobShops are Hard to Approximate

• Monaldo Mastrolilli
• Ola Svensson

For every euro > 0, we show that the (acyclic) job shop problem cannot be approximated within ratio O(log 1+euro lb), unless NP has quasi-polynomial Las-Vegas algorithms, and where lb denotes a trivial lower bound on the optimal value. This almost matches the best known results for acyclic job shops, since an O(log 1+euro lb)-approximate solution can be obtained in polynomial time for every euro > 0. Recently, a PTAS was given for the job shop problem, where the number of machines and the number of operations per job are assumed to be constant. Under P ne NP, and when the number mu of operations per job is a constant, we provide an inapproximability result whose value grows with mu to infinity. Moreover, we show that the problem with two machines and the preemptive variant with three machines have no PTAS, unless NP has quasi-polynomial algorithms. These results show that the restrictions on the number of machines and operations per job are necessary to obtain a PTAS. In summary, the presented results close many gaps in our understanding of the hardness of the job shop problem and resolve (negatively) several open problems in the literature.

FOCS Conference 2007 Conference Paper

Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling

• Christoph Ambühl
• Monaldo Mastrolilli
• Ola Svensson

We consider (uniform) sparsest cut, optimal linear arrangement and the precedence constrained scheduling problem 1 |prec| Sigmaw j C j -So far, these three notorious NP-hard problems have resisted all attempts to prove inapproximability results. We show that they have no polynomial time approximation scheme (PTAS), unless NP-complete pmblems can be solved in randomized subexponential time. Furthermore, we prove that the scheduling problem is as-hard to approximate as vertex cover when the so-called fixed cost, that is present in all feasible solutions, is subtracted from the objective function.