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

DOI10.1007/S00224-009-9235-1zbMATH Open1203.68315OpenAlexW1992598798MaRDI QIDQ968274FDOQ968274

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

Recommendations

• Small Space Representations for Metric Min-Sum k-Clustering and Their Applications
• Approximating min-sum k -clustering in metric spaces
• On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
• On coresets for k-means and k-median clustering
• Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median

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)

Cites Work

• Property testing and its connection to learning and approximation
• Title not available (Why is that?)
• P-Complete Approximation Problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Sublinear time algorithms for metric space problems
• Profit-earning facility location
• Optimal time bounds for approximate clustering
• Approximate clustering via core-sets
• On coresets for k-means and k-median clustering
• Approximation schemes for clustering problems
• On k-Median clustering in high dimensions
• Title not available (Why is that?)
• Abstract Combinatorial Programs and Efficient Property Testers
• Smaller coresets for \(k\)-median and \(k\)-means clustering
• Approximation algorithms for min-sum \(p\)-clustering
• Title not available (Why is that?)
• On average distortion of embedding metrics into the line and into L ₁
• Title not available (Why is that?)
• Approximating min-sum k -clustering in metric spaces
• A randomized approximation scheme for metric MAX-CUT
• Coresets in dynamic geometric data streams
• Clustering for edge-cost minimization (extended abstract)
• Quick k-Median, k-Center, and Facility Location for Sparse Graphs
• Automata, Languages and Programming
• Memoryless Facility Location in One Pass
• Better streaming algorithms for clustering problems
• Testing of Clustering
• Tolerant property testing and distance approximation
• Projective clustering in high dimensions using core-sets
• Advances in metric embedding theory
• A \(k\)-median algorithm with running time independent of data size
• Sublinear‐time approximation algorithms for clustering via random sampling
• Algorithms for dynamic geometric problems over data streams
• Geometric algorithms for the minimum cost assignment problem
• Sublinear time approximate clustering
• Automata, Languages and Programming

Cited In (4)

• Sublinear-time Algorithms
• Approximating min-sum k -clustering in metric spaces
• Title not available (Why is that?)
• Constant-Factor FPT Approximation for Capacitated k-Median

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

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