Accurate Low-Space Approximation of Metric k-Median for Insertion-Only Streams

DOI10.1007/978-3-319-53007-9_7zbMath1485.68315OpenAlexW2585329712MaRDI QIDQ2971636

Harry Lang, Keith Levin, Vladimir Braverman

Publication date: 7 April 2017

Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-53007-9_7

zbMATH Keywords

clusteringstreaming algorithms\(k\)-median

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Smaller coresets for \(k\)-median and \(k\)-means clustering
• BICO: BIRCH Meets Coresets for k-Means Clustering
• On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
• Approximate clustering via core-sets
• On coresets for k-means and k-median clustering
• Better streaming algorithms for clustering problems
• Decomposable searching problems I. Static-to-dynamic transformation
• Profit-earning facility location
• An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
• A unified framework for approximating and clustering data

This page was built for publication: Accurate Low-Space Approximation of Metric k-Median for Insertion-Only Streams