Algorithms for stable and perturbation-resilient problems

DOI10.1145/3055399.3055487zbMath1370.68115OpenAlexW2626597900MaRDI QIDQ4977992

Haris Angelidakis, Konstantin Makarychev, Yury Makarychev

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3055399.3055487

zbMATH Keywords

stability\(k\)-meansperturbation resilience\(k\)-median

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (12)

Solving \((k-1)\)-stable instances of \texttt{k-terminal cut} with isolating cuts ⋮ Strategyproof facility location in perturbation stable instances ⋮ An exact algorithm for stable instances of the \(k\)-means problem with penalties in fixed-dimensional Euclidean space ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On semi-supervised active clustering of stable instances with oracles ⋮ Robust \(k\)-center with two types of radii ⋮ Mechanism design for perturbation stable combinatorial auctions ⋮ Robust \(k\)-center with two types of radii ⋮ On perturbation resilience of non-uniform \(k\)-center ⋮ Stability and Recovery for Independence Systems

This page was built for publication: Algorithms for stable and perturbation-resilient problems