Polynomial Time Algorithm for 2-Stable Clustering Instances

2016/07/25 by Ainesh Bakshi, Bakshi, Ainesh, Nadiia Chepurko +1
Business, Management and Accounting · Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Facility Location and Emergency Management #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1607.07431

openalex publication_date 2016/07/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Clustering with most objective functions is NP-Hard, even to approximate well in the worst case. Recently, there has been work on exploring different notions of stability which lend structure to the problem. The notion of stability, α-perturbation resilience, that we study in this paper was originally introduced by Bilu et al.~\citeBilu10. The works of Awasthi et al~\citeAwasthi12 and Balcan et al.~\citeBalcan12 provide a polynomial time algorithm for 3-stable and (1+√(2))-stable instances respectively. This paper provides a polynomial time algorithm for 2-stable instances, improving on and answering an open question in ~\citeBalcan12.

Citations

• Local Search Heuristics for k-Median and Facility Location Problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Least squares quantization in PCM

Related

• Data Stability in Clustering: A Closer Look
• Clustering under Local Stability: Bridging the Gap between Worst-Case and Beyond Worst-Case Analysis
• Clustering under Perturbation Stability in Near-Linear Time
• Clustering under Perturbation Resilience
• Center-based Clustering under Perturbation Stability