32 citations · 57 across the 8 of their papers we have counts for
Showing 2012Show all
2 papers · 1 filter
cs.DS2012★ 4 cited
Approximating -Median via Pseudo-Approximation
Shi Li, Ola Svensson
We present a novel approximation algorithm for -median that achieves an approximation guarantee of , improving upon the decade-old ratio of . Our approach is…
cs.DS2012★ 32 cited
A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
Julia Chuzhoy, Shi Li
In the Edge-Disjoint Paths with Congestion problem (EDPwC), we are given an undirected n-vertex graph G, a collection M={(s_1,t_1),...,(s_k,t_k)} of demand pairs and an integer c.…