Sublinear‐time approximation algorithms for clustering via random sampling

DOI10.1002/rsa.20157zbMath1105.62066OpenAlexW4242408666MaRDI QIDQ3419620

Christian Sohler, Artur Czumaj

Publication date: 7 February 2007

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20157

zbMATH Keywords

clusteringrandom sampling\(k\)-means\(k\)-medianmin-sum clustering

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Approximation algorithms (68W25)

Related Items

On random perfect matchings in metric spaces with not-too-large diameters ⋮ On the properties of reachability, observability, controllability, and constructibility of discrete-time positive time-invariant linear systems with aperiodic choice of the sampling instants ⋮ Small space representations for metric min-sum \(k\)-clustering and their applications ⋮ Sublinear-time Algorithms ⋮ Unnamed Item ⋮ A FAST k-MEANS IMPLEMENTATION USING CORESETS ⋮ An update algorithm for restricted random walk clustering for dynamic data sets ⋮ A sublinear-time approximation scheme for bin packing

Cites Work

• Unnamed Item
• Unnamed Item
• On approximate geometric \(k\)-clustering
• Sublinear time algorithms for metric space problems
• Clustering for edge-cost minimization (extended abstract)
• Approximate clustering via core-sets
• On coresets for k-means and k-median clustering
• Approximation schemes for clustering problems
• Better streaming algorithms for clustering problems
• Coresets in dynamic geometric data streams
• Approximating min-sum k -clustering in metric spaces
• Automata, Languages and Programming