Are stable instances easy? Export

@article{citeulike:4899980, 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.}, archivePrefix = {arXiv}, author = {Bilu, Yonatan and Linial, Nathan}, citeulike-article-id = {4899980}, citeulike-linkout-0 = {http://arxiv.org/abs/0906.3162}, citeulike-linkout-1 = {http://arxiv.org/pdf/0906.3162}, day = {17}, eprint = {0906.3162}, keywords = {approximation, complexity, interesting}, month = {Jun}, posted-at = {2009-06-19 05:03:01}, priority = {4}, title = {Are stable instances easy?}, url = {http://arxiv.org/abs/0906.3162}, year = {2009} }

TY - JOUR ID - citeulike:4899980 L3 - citeulike-article-id:4899980 N2 - 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. TI - Are stable instances easy? KW - approximation KW - complexity KW - interesting AU - Bilu, Yonatan AU - Linial, Nathan PY - 2009/Jun/17/ UR - http://arxiv.org/abs/0906.3162 ER -