On perturbation resilience of non-uniform \(k\)-center

DOI10.1007/s00453-021-00887-8OpenAlexW3210706484MaRDI QIDQ2072096

Sayan Bandyapadhyay

Publication date: 1 February 2022

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

stabilityclusteringperturbation resiliencenon-uniform \(k\)-center

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Center-based clustering under perturbation stability
• The firefighter problem for cubic graphs
• Clustering to minimize the maximum intercluster distance
• NP is as easy as detecting unique solutions
• Embedding tree metrics into low-dimensional Euclidean spaces
• \(k\)-means++ under approximation stability
• The firefighter problem for graphs of maximum degree three
• Are Stable Instances Easy?
• On the Complexity of the Metric TSP under Stability Considerations
• Asymmetric k -center is log ^* n -hard to approximate
• A Best Possible Heuristic for the k-Center Problem
• Firefighting on Trees Beyond Integrality Gaps
• k-Center Clustering Under Perturbation Resilience
• Approximate Clustering via Metric Partitioning
• An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
• Algorithms for stable and perturbation-resilient problems
• Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
• Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-MEANS
• Bilu–Linial Stable Instances of Max Cut and Minimum Multiway Cut
• The effectiveness of lloyd-type methods for the k-means problem
• The complexity of satisfiability problems
• The Non-Uniform k -Center Problem
• Clustering under Perturbation Resilience

This page was built for publication: On perturbation resilience of non-uniform \(k\)-center