Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR09-057 | 23rd June 2009 00:00

Are stable instances easy?

RSS-Feed




TR09-057
Authors: Yonatan Bilu, Nathan Linial
Publication: 6th July 2009 19:22
Downloads: 1452
Keywords: 


Abstract:

We 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.



ISSN 1433-8092 | Imprint