Small space representations for metric min-sum \(k\)-clustering and their applications

DOI10.1007/s00224-009-9235-1zbMath1203.68315OpenAlexW1992598798MaRDI 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

zbMATH Keywords

clusteringstreaming algorithmscoresetssublinear-time algorithmsbalanced \(k\)-medianmin-sum \(k\)-clusteringsublinear-space algorithms

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Approximation algorithms (68W25)

Related Items (3)

Sublinear-time Algorithms ⋮ Unnamed Item ⋮ Constant-Factor FPT Approximation for Capacitated k-Median

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 ₁
• 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

This page was built for publication: Small space representations for metric min-sum \(k\)-clustering and their applications