Small space representations for metric min-sum \(k\)-clustering and their applications
type: Item
instance of: scholarly article
title: Small space representations for metric min-sum \(k\)-clustering and their applications
zbMATH Open document ID: 1203.68315
author: Artur Czumaj
author: Christian Sohler
published in: Theory of Computing Systems
publication date: 2010-05-05T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 62H30
Mathematics Subject Classification ID: 68T05
zbMATH DE Number: 5703837
zbMATH Keywords: sublinear-time algorithms
zbMATH Keywords: sublinear-space algorithms
zbMATH Keywords: clustering
zbMATH Keywords: min-sum \(k\)-clustering
zbMATH Keywords: balanced \(k\)-median
zbMATH Keywords: streaming algorithms
zbMATH Keywords: coresets
MaRDI profile type: Publication
full work available at URL: s00224-009-9235-1
OpenAlex ID: W1992598798
cites work: Advances in metric embedding theory
cites work: Testing of Clustering
cites work: Q5290249
cites work: Automata, Languages and Programming
cites work: Approximate clustering via core-sets
cites work: Approximating min-sum k -clustering in metric spaces
cites work: Q4527030
cites work: Better streaming algorithms for clustering problems
cites work: On k-Median clustering in high dimensions
cites work: Abstract Combinatorial Programs and Efficient Property Testers
cites work: Sublinear‐time approximation algorithms for clustering via random sampling
cites work: Q3396583
cites work: Approximation schemes for clustering problems
cites work: A randomized approximation scheme for metric MAX-CUT
cites work: Memoryless Facility Location in One Pass
cites work: Coresets in dynamic geometric data streams
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Property testing and its connection to learning and approximation
cites work: Approximation algorithms for min-sum \(p\)-clustering
cites work: On coresets for k-means and k-median clustering
cites work: Smaller coresets for \(k\)-median and \(k\)-means clustering
cites work: Projective clustering in high dimensions using core-sets
cites work: Sublinear time algorithms for metric space problems
cites work: Algorithms for dynamic geometric problems over data streams
cites work: Optimal time bounds for approximate clustering
cites work: Profit-earning facility location
cites work: A \(k\)-median algorithm with running time independent of data size
cites work: Sublinear time approximate clustering
cites work: Q3425115
cites work: Tolerant property testing and distance approximation
cites work: On average distortion of embedding metrics into the line and into L 1
cites work: P-Complete Approximation Problems
cites work: Clustering for edge-cost minimization (extended abstract)
cites work: Quick k-Median, k-Center, and Facility Location for Sparse Graphs
cites work: Geometric algorithms for the minimum cost assignment problem
DOI: 10.1007/S00224-009-9235-1
description: scientific article; zbMATH DE number 5703837