Algorithms for stable and perturbation-resilient problems

DOI10.1145/3055399.3055487MaRDI QIDQ4977992zbMATH OpenOpenAlexFDO

Authors 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

\(k\)-means\(k\)-medianperturbation resiliencestability

Mathematics Subject Classification ID

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

Recommendations

• Center-based clustering under perturbation stability
• Data stability in clustering: a closer look
• \(k\)-center clustering under perturbation resilience
• Data stability in clustering: a closer look
• \(k\)-center clustering under perturbation resilience

Cited in

(24)

• On perturbation resilience of non-uniform k-center
• 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
• On semi-supervised active clustering of stable instances with oracles
• Parameterized resiliency problems
• Data stability in clustering: a closer look
• Bilu-Linial stability
• Robust algorithms for restricted domains
• \(k\)-center clustering under perturbation resilience
• \(k\)-center clustering under perturbation resilience
• scientific article; zbMATH DE number 7378621 (Why is no real title available?)
• Perturbation Resilience
• Bilu-Linial stability, certified algorithms and the independent set problem
• Stability and recovery for independence systems
• Parameterized resiliency problems via integer linear programming
• Bilu-Linial stable instances of max cut and minimum multiway cut
• Robust \(k\)-center with two types of radii
• Mechanism design for perturbation stable combinatorial auctions
• Robust \(k\)-center with two types of radii
• scientific article; zbMATH DE number 7758333 (Why is no real title available?)
• Clustering under perturbation stability in near-linear time
• Exact algorithms and lower bounds for stable instances of Euclidean k-means
• Center-based clustering under perturbation stability

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4977992)