On bounded occurrence constraint satisfaction

被引：9

作者：

Håstad, J ^{[1
]}

机构：

[1] Royal Inst Technol, Dept Math, S-10044 Stockholm, Sweden

来源：

INFORMATION PROCESSING LETTERS | 2000年 / 74卷 / 1-2期

关键词：

analysis of algorithms; computational complexity; approximation algorithms;

D O I：

10.1016/S0020-0190(00)00032-6

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

An approximation algorithm for a constraint satisfaction problem is said to be nontrivial if its performance ratio is strictly superior to the expected performance of the algorithm which simply chooses a random assignment. We prove that any constraint satisfaction problem where each variable appears a bounded number of times admits a nontrivial polynomial time approximation algorithm. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：1 / 6

页数：6

共 11 条

[1] Andersson G, 1999, PROCEEDINGS OF THE TENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P41
[2] Ausiello G, 1999, COMPLEXITY APPROXIMA, DOI DOI 10.1007/978-3-642-58412-1
[3] BERMAN P, SPRINGER LECT NOTES, V1644, P200
[4] A threshold of in n for approximating set cover
Feige, U
[J]. JOURNAL OF THE ACM, 1998, 45 (04) : 634 - 652
[5] Feige U., 1995, Proceedings Third Israel Symposium on the Theory of Computing and Systems, P182, DOI 10.1109/ISTCS.1995.377033
[6] Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Goemans, MX
Williamson, DP
[J]. JOURNAL OF THE ACM, 1995, 42 (06) : 1115 - 1145
[7] HASTAD J, 1997, P 29 ANN ACM S THEOR, P1
[8] APPROXIMATION ALGORITHMS FOR COMBINATORIAL PROBLEMS
JOHNSON, DS
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1974, 9 (03) : 256 - 278
[9] OPTIMIZATION, APPROXIMATION, AND COMPLEXITY CLASSES
PAPADIMITRIOU, CH
YANNAKAKIS, M
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1991, 43 (03) : 425 - 440
[10] TREVISAN L, COMMUNICATION

← 1 2 →