Are Stable Instances Easy?

DOI10.1017/S0963548312000193zbMath1283.68153OpenAlexW2119265025MaRDI QIDQ2911066

Yonatan Bilu, Nathan Linial

Publication date: 12 September 2012

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548312000193

zbMATH Keywords

NP-hard problempolynomial-time solvable instancesstability of instances

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (21)

Solving \((k-1)\)-stable instances of \texttt{k-terminal cut} with isolating cuts ⋮ Preclustering algorithms for imprecise points ⋮ An exact algorithm for stable instances of the \(k\)-means problem with penalties in fixed-dimensional Euclidean space ⋮ Perturbation resilience for the facility location problem ⋮ An Experimental Study of Algorithms for Online Bipartite Matching ⋮ Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry ⋮ Pareto robust optimization on Euclidean vector spaces ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics ⋮ Robust optimization in the presence of uncertainty: a generic approach ⋮ Unnamed Item ⋮ On semi-supervised active clustering of stable instances with oracles ⋮ Good (K-means) clusterings are unique (up to small perturbations) ⋮ Unnamed Item ⋮ Smooth and strong PCPs ⋮ Mechanism design for perturbation stable combinatorial auctions ⋮ Center-based clustering under perturbation stability ⋮ Finding Meaningful Cluster Structure Amidst Background Noise ⋮ On perturbation resilience of non-uniform \(k\)-center ⋮ Stability and Recovery for Independence Systems

Cites Work

• Unnamed Item
• The ellipsoid method and its consequences in combinatorial optimization
• Laplacian eigenvalues and the maximum cut problem
• The Metropolis algorithm for graph bisection
• Heuristics for semirandom graph problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

This page was built for publication: Are Stable Instances Easy?