6 citations · 14 across the 22 of their papers we have counts for
Showing 2016 · cs.DSShow all
3 papers · 2 filters
cs.DS2016
A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs
Zachary Friggstad, Jochen Koenemann, Mohammad Shadravan
We demonstrate that the integrality gap of the natural cut-based LP relaxation for the directed Steiner tree problem is in quasi-bipartite graphs with terminals. Su…
cs.DS2016★ 6 cited
Tight Analysis of a Multiple-Swap Heuristic for Budgeted Red-Blue Median
Zachary Friggstad, Yifeng Zhang
Budgeted Red-Blue Median is a generalization of classic -Median in that there are two sets of facilities, say and , that can be used to serve clients…
cs.DS2016
Local Search Yields a PTAS for k-Means in Doubling Metrics
Zachary Friggstad, Mohsen Rezapour, Mohammad R. Salavatipour
The most well known and ubiquitous clustering problem encountered in nearly every branch of science is undoubtedly -means: given a set of data points and a parameter , select…