REVIEW 3 cited by
Faster and Simpler Greedy Algorithm for $k$-Median and $k$-Means
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
Clustering problems such as $k$-means and $k$-median are staples of unsupervised learning, and many algorithmic techniques have been developed to tackle their numerous aspects. In this paper, we focus on the class of greedy approximation algorithm, that attracted less attention than local-search or primal-dual counterparts. In particular, we study the recursive greedy algorithm developed by Mettu and Plaxton [SIAM J. Comp 2003]. We provide a simplification of the algorithm, allowing for faster implementation, in graph metrics or in Euclidean space, where our algorithm matches or improves the state-of-the-art.
Forward citations
Cited by 3 Pith papers
-
Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
Streaming algorithms for (k,z)-clustering and Lp subspace embeddings can match offline algorithms in space and time, removing all dependence on stream length n.
-
Faster Randomized and Deterministic k-Clustering on Graphs
New deterministic and randomized algorithms achieve near-linear-time constant-factor approximations for k-center and (k,z)-clustering on graphs, resolving an open problem of Abboud et al.
-
Faster Approximation Algorithms for k-Center via Data Reduction
For Euclidean k-center with k=n^c, the paper gives an O(1)-approximation in near-linear time by building small coresets via a new efficient consistent hashing.
Discussion (0). Continue with ORCID to comment.