Algorithms for stable and perturbation-resilient problems

DOI10.1145/3055399.3055487zbMATH Open1370.68115OpenAlexW2626597900MaRDI QIDQ4977992FDOQ4977992

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

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

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)

Cited In (13)

• On semi-supervised active clustering of stable instances with oracles
• Title not available (Why is that?)
• Mechanism design for perturbation stable combinatorial auctions
• Stability and Recovery for Independence Systems
• Title not available (Why is that?)
• Robust \(k\)-center with two types of radii
• Robust \(k\)-center with two types of radii
• Title not available (Why is that?)
• 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
• On perturbation resilience of non-uniform \(k\)-center
• Solving \((k-1)\)-stable instances of \texttt{k-terminal cut} with isolating cuts

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)