ECCC-Report TR09-057https://eccc.weizmann.ac.il/report/2009/057Comments and Revisions published for TR09-057en-usMon, 06 Jul 2009 19:22:05 +0300
Paper TR09-057
| Are stable instances easy? |
Yonatan Bilu,
Nathan Linial
https://eccc.weizmann.ac.il/report/2009/057We introduce the notion of a stable instance for a discrete
optimization problem, and argue that in many practical situations
only sufficiently stable instances are of interest. The question
then arises whether stable instances of NP--hard problems are
easier to solve. In particular, whether there exist algorithms
that solve correctly and in polynomial time all sufficiently
stable instances of some NP--hard problem. The paper focuses on
the Max--Cut problem, for which we show that this is indeed the
case.
Mon, 06 Jul 2009 19:22:05 +0300https://eccc.weizmann.ac.il/report/2009/057