Center-based clustering under perturbation stability

DOI10.1016/J.IPL.2011.10.006zbMATH Open1233.68233arXiv1009.3594OpenAlexW1558625102MaRDI QIDQ763489FDOQ763489

Authors: Pranjal Awasthi, Or Sheffet, Avrim Blum 

Publication date: 9 March 2012

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

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.

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

Recommendations

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

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)

Cites Work

• The effectiveness of lloyd-type methods for the k-means problem
• Title not available (Why is that?)
• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A new greedy approach for facility location problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Local search heuristic for k-median and facility location problems
• A Sober Look at Clustering Stability
• Approximation schemes for clustering problems
• Approximating min-sum k -clustering in metric spaces
• Title not available (Why is that?)
• Clustering under approximation stability
• Center-based clustering under perturbation stability
• Stability of k-Means Clustering
• Are stable instances easy?

Cited In (30)

• On semi-supervised active clustering of stable instances with oracles
• Title not available (Why is that?)
• On the Complexity of the Metric TSP under Stability Considerations
• Title not available (Why is that?)
• Mechanism design for perturbation stable combinatorial auctions
• One-dimensional center-based l 1-clustering method
• Title not available (Why is that?)
• Partitioning Well-Clustered Graphs: Spectral Clustering Works!
• Stability and Recovery for Independence Systems
• Title not available (Why is that?)
• Robust \(k\)-center with two types of radii
• Robust \(k\)-center with two types of radii
• Smooth and strong PCPs
• Preprocessing to reduce the search space: antler structures for feedback vertex set
• Approximate Clustering with Same-Cluster Queries
• Title not available (Why is that?)
• Data stability in clustering: a closer look
• Data stability in clustering: a closer look
• Clustering under Perturbation Resilience
• Center-based clustering under perturbation stability
• A quantization framework for smoothed analysis of Euclidean optimization problems
• Perturbation resilience for the facility location problem
• An exact algorithm for stable instances of the \(k\)-means problem with penalties in fixed-dimensional Euclidean space
• Preprocessing to reduce the search space: antler structures for feedback vertex set
• Strategyproof facility location in perturbation stable instances
• Finding Meaningful Cluster Structure Amidst Background Noise
• On perturbation resilience of non-uniform \(k\)-center
• Multi-central general type-2 fuzzy clustering approach for pattern recognitions
• Reverse greedy is bad for \(k\)-center
• Clustering with or without the approximation

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)