Some optimal inapproximability results

被引：823

作者：

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
AMALDI, E
KANN, V
[J]. 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
Arora, S
Lund, C
Motwani, R
Sudan, M
Szegedy, M
[J]. JOURNAL OF THE ACM, 1998, 45 (03) : 501 - 555
[5] Probabilistic checking of proofs: A new characterization of NP
Arora, S
Safra, S
[J]. 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
BARYEHUDA, R
EVEN, S
[J]. 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
Bellare, M
Goldreich, O
Sudan, M
[J]. SIAM JOURNAL ON COMPUTING, 1998, 27 (03) : 804 - 915

← 1 2 3 4 →