42 citations · 204 across the 38 of their papers we have counts for
5 papers · 1 filter
Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
Nikhil Bansal, 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 -approximation algorithm for…
Constant Factor Approximation for ATSP with Two Edge Weights
Ola Svensson, Jakub Tarnawski, László A. Végh
We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the…
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…
No Small Linear Program Approximates Vertex Cover within a Factor
Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta +1
The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev (2003) proved that the problem is NP-hard to appro…
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 re…