• German
German

Main Navigation

Sohler/Woodruff/2018a: Strong Coresets for $k$-Median and Subspace Approximation: Goodbye Dimension

Bibtype Inproceedings
Bibkey Sohler/Woodruff/2018a
Author Sohler, Christian and Woodruff, David P.
Editor Thorup, Mikkel
Title Strong Coresets for $k$-Median and Subspace Approximation: Goodbye Dimension
Booktitle 59th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
Pages 802--813
Publisher {IEEE} Computer Society
Abstract We obtain the first strong coresets for the $k$-median and subspace approximation problems with sum of distances objective function, on $n$ points in $d$ dimensions, with a number of weighted points that is independent of both $n$ and $d$; namely, our coresets have size $poly(k/\eps)$. A strong coreset $(1 + \eps)$-approximates the cost function for all possible sets of centers simultaneously. We also give
efficient $nnz(A)+(n+d)poly(k/\eps)+exp(poly(k/\eps))$ time algorithms for computing these coresets.

We obtain the result by introducing a new dimensionality reduction technique for coresets that significantly generalizes an earlier result of Feldman, Sohler and Schmidt for squared Euclidean distances to sums of $p$-th powers of Euclidean distances for constant $p\geq 1$.
Year 2018
Projekt SFB876-A2
Url https://doi.org/10.1109/FOCS.2018.00081
Bibtex Here you can get this literature entry as BibTeX format.