Clustering under Perturbation Resilience

DOI10.1007/978-3-642-31594-7_6zbMath1272.68340arXiv1112.0826OpenAlexW1588576489MaRDI QIDQ5891120

Maria-Florina Balcan, Yingyu Liang

Publication date: 12 August 2013

Published in: SIAM Journal on Computing, Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1112.0826

zbMATH Keywords

clusteringperturbation resilience\(k\)-medianmin-sum\(k\)-median clusteringmin-sum clustering

Mathematics Subject Classification ID

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

Related Items (12)

Strategyproof facility location in perturbation stable instances ⋮ An exact algorithm for stable instances of the \(k\)-means problem with penalties in fixed-dimensional Euclidean space ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Data stability in clustering: a closer look ⋮ Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics ⋮ Unnamed Item ⋮ On semi-supervised active clustering of stable instances with oracles ⋮ Reverse greedy is bad for \(k\)-center ⋮ Finding Meaningful Cluster Structure Amidst Background Noise ⋮ On perturbation resilience of non-uniform \(k\)-center ⋮ Stability and Recovery for Independence Systems

This page was built for publication: Clustering under Perturbation Resilience