A k-median algorithm with running time independent of data size

DOI10.1023/B:MACH.0000033115.78247.F0MaRDI QIDQ703077zbMATH OpenOpenAlexFDO

Authors Adam Meyerson, Liadan O'Callaghan, Serge Plotkin

Publication date 19 January 2005

Published in Machine Learning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/b:mach.0000033115.78247.f0

zbMATH Keywords

Clusteringsamplingsublinear

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Nonnumerical algorithms (68W05)

Recommendations

• Optimal time bounds for approximate clustering
• Learning Theory
• Automata, Languages and Programming
• A framework for statistical clustering with constant time approximation algorithms for \(K\)-median and \(K\)-means clustering
• On coresets for k-means and k-median clustering

Cited in

(21)

• Attainable accuracy guarantee for the \(k\)-medians clustering in [0, 1]
• Near-optimal clustering in the \(k\)-machine model
• Clustering with or without the approximation
• A framework for statistical clustering with constant time approximation algorithms for \(K\)-median and \(K\)-means clustering
• A new efficient algorithm based on DC programming and DCA for clustering
• Mathematical programming formulations and algorithms for discrete k-median clustering of time-series data
• Clustering with or without the approximation
• Learning Theory
• scientific article; zbMATH DE number 2090269 (Why is no real title available?)
• Sublinear-time Algorithms
• Robust communication-optimal distributed clustering algorithms
• An experimental evaluation of incremental and hierarchical \(k\)-median algorithms
• Automata, Languages and Programming
• Data reduction for weighted and outlier-resistant clustering
• scientific article; zbMATH DE number 7651177 (Why is no real title available?)
• Bi-criteria sublinear time algorithms for clustering with outliers in high dimensions
• Online k-Median with consistent clusters
• Bi-criteria sublinear time algorithms for clustering with outliers in high dimensions
• Optimal time bounds for approximate clustering
• Relational algorithms for k-means clustering
• Small space representations for metric min-sum k-clustering and their applications

This page was built for publication: A \(k\)-median algorithm with running time independent of data size

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