O. Svensson

activity

20102023

1/2

-Approximation for Submodular Maximization on Massive Data Streams

42 citations · 204 across the 38 of their papers we have counts for

collaborators

Showing 2012Show all

3 papers · 1 filter

cs.DS2012★ 4 cited

Approximating $k$ -Median via Pseudo-Approximation

Shi Li, 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…

cs.CC2012★ 12 cited

Hardness of Vertex Deletion and Project Scheduling

Ola Svensson

Assuming the Unique Games Conjecture, we show strong inapproximability results for two natural vertex deletion problems on directed graphs: for any integer $k \geq 2$ and arbitrary…

cs.DS2012★ 5 cited

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

Lukas Polacek, Ola Svensson

The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estima…

Approximating k-Median via Pseudo-Approximation

Hardness of Vertex Deletion and Project Scheduling

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

Approximating $k$ -Median via Pseudo-Approximation