On the hardness of approximating minimum vertex cover

被引：372

作者：

Dinur, I

Safra, S

机构：

[1] Univ Calif Berkeley, Miller Inst, Berkeley, CA 94720 USA

[2] Tel Aviv Univ, Sch Comp Sci, IL-69978 Tel Aviv, Israel

来源：

ANNALS OF MATHEMATICS | 2005年 / 162卷 / 01期

关键词：

D O I：

10.4007/annals.2005.162.439

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove the Minimum Vertex Cover problem to be NP-hard to approximate to within a factor of 1.3606, extending on previous PCP and hardness of approximation technique. To that end, one needs to develop a new proof framework, and to borrow and extend ideas from several fields.

引用

收藏

页码：439 / 485

页数：47

相关论文

共 47 条

[1] The complete intersection theorem for systems of finite sets [J].

Ahlswede, R ;

Khachatrian, LH .

EUROPEAN JOURNAL OF COMBINATORICS, 1997, 18 (02) :125-136

[2]

Ajtai M., 1998, STOC, P10

[3]

[Anonymous], I HAUTES ETUDES SCI

[4]

[Anonymous], PLENUM COMPLEXITY CO

[5] The hardness of approximate optima in lattices, codes, and systems of linear equations [J].

Arora, S ;

Babai, L ;

Stern, J ;

Sweedyk, Z .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1997, 54 (02) :317-331

[6] Proof verification and the hardness of approximation problems [J].

Arora, S ;

Lund, C ;

Motwani, R ;

Sudan, M ;

Szegedy, M .

JOURNAL OF THE ACM, 1998, 45 (03) :501-555

[7] Probabilistic checking of proofs: A new characterization of NP [J].

Arora, S ;

Safra, S .

JOURNAL OF THE ACM, 1998, 45 (01) :70-122

[8]

ARORA S, COMMUNICATION

[9]

Bar-Yehuda R., 1985, ANN DISCRETE MATH, V25, P27, DOI DOI 10.1016/S0304-0208(08)73101-3

[10] Free bits, PCPs, and nonapproximability - Towards tight results [J].

Bellare, M ;

Goldreich, O ;

Sudan, M .

SIAM JOURNAL ON COMPUTING, 1998, 27 (03) :804-915

← 1 2 3 4 5 →