42 citations · 204 across the 38 of their papers we have counts for
Showing 2017Show all
3 papers · 1 filter
cs.DS2017
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 (ATSP). Our approximation guarantee is analyzed with respect to the standard LP rela…
cs.DS2017
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…
cs.CC2017★ 14 cited
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 time on $n^{O(\log^2 n)}…