Center-based clustering under perturbation stability

DOI10.1016/J.IPL.2011.10.006MaRDI QIDQ763489zbMATH OpenOpenAlexFDO

Authors Pranjal Awasthi, Or Sheffet, Avrim Blum

Publication date 9 March 2012

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

clusteringstability conditions\(k\)-meansanalysis of algorithms\(k\)-median

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: Clustering under most popular objective functions is NP-hard, even to approximate well, and so unlikely to be efficiently solvable in the worst case. Recently, Bilu and Linial cite{Bilu09} suggested an approach aimed at bypassing this computational barrier by using properties of instances one might hope to hold in practice. In particular, they argue that instances in practice should be stable to small perturbations in the metric space and give an efficient algorithm for clustering instances of the Max-Cut problem that are stable to perturbations of size $O(n^{1/2})$. In addition, they conjecture that instances stable to as little as O(1) perturbations should be solvable in polynomial time. In this paper we prove that this conjecture is true for any center-based clustering objective (such as $k$-median, $k$-means, and $k$-center). Specifically, we show we can efficiently find the optimal clustering assuming only stability to factor-3 perturbations of the underlying metric in spaces without Steiner points, and stability to factor $2+sqrt3$ perturbations for general metrics. In particular, we show for such instances that the popular Single-Linkage algorithm combined with dynamic programming will find the optimal clustering. We also present NP-hardness results under a weaker but related condition.

Recommendations

• Data stability in clustering: a closer look
• Data stability in clustering: a closer look
• Algorithms for stable and perturbation-resilient problems

Cites work

• scientific article; zbMATH DE number 5485537 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256748 (Why is no real title available?)
• scientific article; zbMATH DE number 1303608 (Why is no real title available?)
• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• scientific article; zbMATH DE number 1775400 (Why is no real title available?)
• scientific article; zbMATH DE number 5485581 (Why is no real title available?)
• A Sober Look at Clustering Stability
• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
• A new greedy approach for facility location problems
• Approximating min-sum k -clustering in metric spaces
• Approximation schemes for clustering problems
• Are stable instances easy?
• Center-based clustering under perturbation stability
• Clustering under approximation stability
• Local search heuristic for k-median and facility location problems
• Stability of k-Means Clustering
• The effectiveness of Lloyd-type methods for the \(k\)-means problem

Cited in

(32)

• Data stability in clustering: a closer look
• On the Complexity of the Metric TSP under Stability Considerations
• Preprocessing to reduce the search space: antler structures for feedback vertex set
• Robust \(k\)-center with two types of radii
• Robust \(k\)-center with two types of radii
• Center-based clustering under perturbation stability
• scientific article; zbMATH DE number 5957421 (Why is no real title available?)
• Bilu-Linial stability
• Smooth and strong PCPs
• Clustering with or without the approximation
• Finding Meaningful Cluster Structure Amidst Background Noise
• On semi-supervised active clustering of stable instances with oracles
• Mechanism design for perturbation stable combinatorial auctions
• Bilu-Linial stability, certified algorithms and the independent set problem
• Multi-central general type-2 fuzzy clustering approach for pattern recognitions
• Stability and recovery for independence systems
• A quantization framework for smoothed analysis of Euclidean optimization problems
• Algorithms for stable and perturbation-resilient problems
• Clustering under approximation stability
• On perturbation resilience of non-uniform \(k\)-center
• Perturbation resilience for the facility location problem
• scientific article; zbMATH DE number 7378621 (Why is no real title available?)
• Preprocessing to reduce the search space: antler structures for feedback vertex set
• Reverse greedy is bad for \(k\)-center
• One-dimensional center-based l 1-clustering method
• Strategyproof facility location in perturbation stable instances
• Approximate Clustering with Same-Cluster Queries
• Data stability in clustering: a closer look
• scientific article; zbMATH DE number 7758333 (Why is no real title available?)
• Partitioning well-clustered graphs: spectral clustering works!
• An exact algorithm for stable instances of the \(k\)-means problem with penalties in fixed-dimensional Euclidean space
• scientific article; zbMATH DE number 6902592 (Why is no real title available?)

This page was built for publication: Center-based clustering under perturbation stability

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