Sublinear‐time approximation algorithms for clustering via random sampling

DOI10.1002/RSA.20157zbMATH Open1105.62066OpenAlexW4242408666MaRDI QIDQ3419620FDOQ3419620

Authors 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

clustering\(k\)-meansrandom sampling\(k\)-medianmin-sum clustering

Mathematics Subject Classification ID

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

Recommendations

• Automata, Languages and Programming
• Sublinear time approximate clustering
• Approximation algorithms for stochastic clustering
• Subquadratic approximation algorithms for clustering problems in high dimensional spaces
• Subquadratic approximation algorithms for clustering problems in high dimensional spaces
• Optimal time bounds for approximate clustering
• Linear-time approximation schemes for clustering problems in any dimensions
• Exact and approximation algorithms for clustering
• Approximation schemes for clustering problems
• scientific article; zbMATH DE number 1303609

Cites work

• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• Approximate clustering via core-sets
• Approximating min-sum k -clustering in metric spaces
• Approximation schemes for clustering problems
• Automata, Languages and Programming
• Better streaming algorithms for clustering problems
• Clustering for edge-cost minimization (extended abstract)
• Coresets in dynamic geometric data streams
• On approximate geometric \(k\)-clustering
• On coresets for k-means and k-median clustering
• Sublinear time algorithms for metric space problems
• Sublinear time approximate clustering

Cited in

(20)

• Deterministic metric 1-median selection with very few queries
• Sublinear-time Algorithms
• Approximation algorithms for stochastic clustering
• On random perfect matchings in metric spaces with not-too-large diameters
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Automata, Languages and Programming
• Training Gaussian mixture models at scale via coresets
• Selective sampling for approximate clustering of very large data sets
• A FAST k-MEANS IMPLEMENTATION USING CORESETS
• Optimal time bounds for approximate clustering
• Sublinear time approximate clustering
• Coresets for kernel clustering
• An update algorithm for restricted random walk clustering for dynamic data sets
• A sublinear-time approximation scheme for bin packing
• Learning Theory
• Small space representations for metric min-sum \(k\)-clustering and their applications
• Small Space Representations for Metric Min-Sum k-Clustering and Their Applications
• Faster sublinear algorithms using conditional sampling
• On parameterized approximation algorithms for balanced clustering
• On the properties of reachability, observability, controllability, and constructibility of discrete-time positive time-invariant linear systems with aperiodic choice of the sampling instants

This page was built for publication: Sublinear‐time approximation algorithms for clustering via random sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3419620)