Some optimal inapproximability results
Top Cited Papers
- 1 July 2001
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 48 (4) , 798-859
- https://doi.org/10.1145/502090.502098
Abstract
We prove optimal, up to an arbitrary ε 0, inapproximability results for Max-E k-Sat for k ≥ 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.Keywords
This publication has 26 references indexed in Scilit:
- Probabilistic checking of proofsJournal of the ACM, 1998
- Linearity testing in characteristic twoIEEE Transactions on Information Theory, 1996
- Approximability of maximum splitting of k-sets and some other Apx-complete problemsInformation Processing Letters, 1996
- Interactive proofs and the hardness of approximating cliquesJournal of the ACM, 1996
- Self-testing/correcting with applications to numerical problemsJournal of Computer and System Sciences, 1993
- Algebraic methods for interactive proof systemsJournal of the ACM, 1992
- IP = PSPACEJournal of the ACM, 1992
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Non-deterministic exponential time has two-prover interactive protocolscomputational complexity, 1991
- A linear-time approximation algorithm for the weighted vertex cover problemJournal of Algorithms, 1981