On the practically interesting instances of MAXCUT

DOI10.4230/LIPICS.STACS.2013.526MaRDI QIDQ2957913zbMATH OpenOpenAlexFDO

Authors Yonatan Bilu, Amit Daniely, Nathan Linial, Michael Saks

Publication date 30 January 2017

Full work available at URL https://arxiv.org/abs/1205.4893

zbMATH Keywords

clusteringhardness in practiceMAXCUTnon-worst-case analysisstability

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)

Abstract: The complexity of a computational problem is traditionally quantified based on the hardness of its worst case. This approach has many advantages and has led to a deep and beautiful theory. However, from the practical perspective, this leaves much to be desired. In application areas, practically interesting instances very often occupy just a tiny part of an algorithm's space of instances, and the vast majority of instances are simply irrelevant. Addressing these issues is a major challenge for theoretical computer science which may make theory more relevant to the practice of computer science. Following Bilu and Linial, we apply this perspective to MAXCUT, viewed as a clustering problem. Using a variety of techniques, we investigate practically interesting instances of this problem. Specifically, we show how to solve in polynomial time distinguished, metric, expanding and dense instances of MAXCUT under mild stability assumptions. In particular, $(1+epsilon)$-stability (which is optimal) suffices for metric and dense MAXCUT. We also show how to solve in polynomial time $Omega(sqrtn)$-stable instances of MAXCUT, substantially improving the best previously known result.

Recommendations

• Are stable instances easy?
• A randomized approximation scheme for metric MAX-CUT
• Bilu-Linial stable instances of max cut and minimum multiway cut
• Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
• On the approximability of Max-Cut

Cited in

(10)

• Strategyproof facility location in perturbation stable instances
• Perturbation resilience for the facility location problem
• Are stable instances easy?
• A general approach to the calculation of stability radii for the max-cut problem with multiple criteria
• scientific article; zbMATH DE number 7378621 (Why is no real title available?)
• Complexity and polynomially solvable special cases of QUBO
• Bilu-Linial stability, certified algorithms and the independent set problem
• Stability and recovery for independence systems
• Bilu-Linial stable instances of max cut and minimum multiway cut
• Exact algorithms and lower bounds for stable instances of Euclidean k-means

This page was built for publication: On the practically interesting instances of MAXCUT

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