Some optimal inapproximability results

被引：850

作者：

Håstad, J ^{[1
]}

机构：

[1] Royal Inst Technol, Dept Numer Anal & Comp Sci, S-10044 Stockholm, Sweden

来源：

JOURNAL OF THE ACM | 2001年 / 48卷 / 04期

关键词：

theory; inapproximability; linear equations; max-sat; NP-hard optimization problems; probabilistically checkable proofs;

D O I：

10.1145/502090.502098

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We prove optimal, up to an arbitrary epsilon > 0, inapproximability results for Max-Ek-Sat for k greater than or equal to 3, maximizing the number of satisfied linear equations in an over-determined system of linear equations modulo a prime p and Set Splitting. As a consequence of these results we get improved lower bounds for the efficient approximability of many optimization problems studied previously. In particular, for Max-E2-Sat, Max-Cut, Max-di-Cut, and Vertex cover.

引用

页码：798 / 859

页数：62

共 32 条

[1] THE COMPLEXITY AND APPROXIMABILITY OF FINDING MAXIMUM FEASIBLE SUBSYSTEMS OF LINEAR RELATIONS [J].

AMALDI, E ;

KANN, V .

THEORETICAL COMPUTER SCIENCE, 1995, 147 (1-2) :181-210

[2]

Andersson G, 1999, PROCEEDINGS OF THE TENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P41

[3]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[4] 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

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

Arora, S ;

Safra, S .

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

[6]

Babai L., 1991, Computational Complexity, V1, P3, DOI 10.1007/BF01200056

[7]

Babai Laszlo, 1991, P 23 ANN ACM S THEOR, P21, DOI [10.1145/103418.103428, DOI 10.1145/103418.103428]

[8] A LINEAR-TIME APPROXIMATION ALGORITHM FOR THE WEIGHTED VERTEX COVER PROBLEM [J].

BARYEHUDA, R ;

EVEN, S .

JOURNAL OF ALGORITHMS, 1981, 2 (02) :198-203

[9]

Bellare M., 1993, Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, P294, DOI 10.1145/167088.167174

[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 →