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

stability\(k\)-means\(k\)-medianperturbation resilience

Mathematics Subject Classification ID

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

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

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)