Are Stable Instances Easy?

被引：44

作者：

Bilu, Yonatan ^{[1
]}

Linial, Nathan ^{[2
]}

机构：

[1] Mobileye Vis Technol Ltd, IL-91450 Jerusalem, Israel

[2] Hebrew Univ Jerusalem, Inst Comp Sci, IL-91904 Jerusalem, Israel

来源：

COMBINATORICS PROBABILITY & COMPUTING | 2012年 / 21卷 / 05期

基金：

以色列科学基金会;

关键词：

GRAPH BISECTION; MAXIMUM CUT; ALGORITHMS; MODEL;

D O I：

10.1017/S0963548312000193

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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, and in particular, whether there exist algorithms that solve 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.

引用

页码：643 / 660

页数：18

共 21 条

[1]

Ackerman M., 2009, Proceedings of AISTATS-09, JMLR, V5, P1

[2]

[Anonymous], 2001, P 33 ANN ACM S THEOR

[3]

Balcan MF, 2009, PROCEEDINGS OF THE TWENTIETH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P1068

[4]

Bilu Y., THESIS

[5]

Boppana R. B., 1987, 28th Annual Symposium on Foundations of Computer Science (Cat. No.87CH2471-1), P280, DOI 10.1109/SFCS.1987.22

[6] GRAPH BISECTION ALGORITHMS WITH GOOD AVERAGE CASE BEHAVIOR [J].

BUI, TN ;

CHAUDHURI, S ;

LEIGHTON, FT ;

SIPSER, M .

COMBINATORICA, 1987, 7 (02) :171-191

[7]

Condon A, 2001, RANDOM STRUCT ALGOR, V18, P116, DOI 10.1002/1098-2418(200103)18:2<116::AID-RSA1001>3.0.CO

[8]

2-2

[9] LAPLACIAN EIGENVALUES AND THE MAXIMUM CUT PROBLEM [J].

DELORME, C ;

POLJAK, S .

MATHEMATICAL PROGRAMMING, 1993, 62 (03) :557-574

[10]

Dyer M. E., 1986, 27 ANN S FDN COMP SC, P313

← 1 2 3 →