42 citations · 202 across the 21 of their papers we have counts for
Showing 2017Show all
3 papers · 1 filter
cs.DS2017★ 14 cited
Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach
Slobodan Mitrović, Ilija Bogunovic, Ashkan Norouzi-Fard +2
We study the classical problem of maximizing a monotone submodular function subject to a cardinality constraint k, with two additional twists: (i) elements arrive in a streaming fa…
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.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)}…