Algorithms for Stable and Perturbation-resilient Problems
summary
Proves that gamma=2 perturbation resilience for k‑means and k‑median implies a center‑proximity property, shows each optimal cluster is a subtree of the metric’s minimum spanning tree, and recovers the exact optimum by running a single‑linkage MST then a bottom‑up dynamic‑program that assigns centers. For multiway cut, shows the standard LP becomes integral under stability and improves previous thresholds to gamma = 2 − 2/k, with constructive proofs and tightness evidence.
AI-written summary · about