Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > MAX CUT:
Reports tagged with max cut:
TR09-057 | 23rd June 2009
Yonatan Bilu, Nathan Linial

Are stable instances easy?

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




ISSN 1433-8092 | Imprint