Sublinear‐time approximation algorithms for clustering via random sampling

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

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

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

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)

Cites Work

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

Cited In (17)

• Sublinear-time Algorithms
• Small space representations for metric min-sum \(k\)-clustering and their applications
• On parameterized approximation algorithms for balanced clustering
• Deterministic metric 1-median selection with very few queries
• An update algorithm for restricted random walk clustering for dynamic data sets
• A sublinear-time approximation scheme for bin packing
• Coresets for kernel clustering
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Sublinear time approximate clustering
• On random perfect matchings in metric spaces with not-too-large diameters
• Learning Theory
• Optimal time bounds for approximate clustering
• Automata, Languages and Programming
• On the properties of reachability, observability, controllability, and constructibility of discrete-time positive time-invariant linear systems with aperiodic choice of the sampling instants
• A FAST k-MEANS IMPLEMENTATION USING CORESETS
• Selective sampling for approximate clustering of very large data sets
• Title not available (Why is that?)

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)