Small space representations for metric min-sum \(k\)-clustering and their applications
From MaRDI portal
Publication:968274
DOI10.1007/s00224-009-9235-1zbMath1203.68315MaRDI QIDQ968274
Christian Sohler, Artur Czumaj
Publication date: 5 May 2010
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-009-9235-1
clustering; streaming algorithms; coresets; sublinear-time algorithms; balanced \(k\)-median; min-sum \(k\)-clustering; sublinear-space algorithms
62H30: Classification and discrimination; cluster analysis (statistical aspects)
68T05: Learning and adaptive systems in artificial intelligence
68W25: Approximation algorithms
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimal time bounds for approximate clustering
- A \(k\)-median algorithm with running time independent of data size
- Smaller coresets for \(k\)-median and \(k\)-means clustering
- Approximation algorithms for min-sum \(p\)-clustering
- A randomized approximation scheme for metric MAX-CUT
- Tolerant property testing and distance approximation
- Sublinear time algorithms for metric space problems
- Property testing and its connection to learning and approximation
- Clustering for edge-cost minimization (extended abstract)
- Sublinear‐time approximation algorithms for clustering via random sampling
- Approximate clustering via core-sets
- On coresets for k-means and k-median clustering
- Algorithms for dynamic geometric problems over data streams
- Approximation schemes for clustering problems
- On average distortion of embedding metrics into the line and into L 1
- Better streaming algorithms for clustering problems
- Coresets in dynamic geometric data streams
- On k-Median clustering in high dimensions
- P-Complete Approximation Problems
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Testing of Clustering
- Projective clustering in high dimensions using core-sets
- Quick k-Median, k-Center, and Facility Location for Sparse Graphs
- Geometric algorithms for the minimum cost assignment problem
- Approximating min-sum k -clustering in metric spaces
- Profit-earning facility location
- Abstract Combinatorial Programs and Efficient Property Testers
- Memoryless Facility Location in One Pass
- Automata, Languages and Programming
- Automata, Languages and Programming
- Advances in metric embedding theory
