2018/09/09 by Christian Sohler, David P. Woodruff, Sohler, Christian +1 · 5 citations
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.DS
paper · pdf · doi:10.48550/arxiv.1809.02961
openalex publication_date 2018/09/09 · arxiv created 2022/04/14 · arxiv updated 2022/04/15 · openalex created_date 2022/08/03 · openalex updated_date 2026/07/28
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/ε). A strong coreset (1+ε)-approximates the cost function for all possible sets of centers simultaneously. We also give efficient nnz(A) + (n+d)poly(k/ε) + exp(poly(k/ε)) 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 \citeFSS13 for squared Euclidean distances to sums of p-th powers of Euclidean distances for constant p≥1.