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}, comment = {Efficiently achieves solutions to instances of an NP complete problem that are stable by (essentially) the same definition as learning theory and boolean function analysis. }, day = {17}, eprint = {0906.3162}, keywords = {graph\_theory, sensitivity, theoretical\_computer\_science}, month = {Jun}, posted-at = {2009-07-02 01:30:02}, priority = {2}, 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 - graph_theory KW - sensitivity KW - theoretical_computer_science N1 - Efficiently achieves solutions to instances of an NP complete problem that are stable by (essentially) the same definition as learning theory and boolean function analysis. AU - Bilu, Yonatan AU - Linial, Nathan PY - 2009/Jun/17/ UR - http://arxiv.org/abs/0906.3162 ER -