article

Some optimal inapproximability results

Author:

Johan HåstadAuthors Info & Claims

Journal of the ACM (JACM), Volume 48, Issue 4

Pages 798 - 859

https://doi.org/10.1145/502090.502098

Published: 01 July 2001 Publication History

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.

References

[1]

AMALDI, E., AND KANN, V. 1995. The complexity and approximability of finding feasible subsystems of linear relations. Theoret. Comput. Sci. 147, 181-210.

Digital Library

[2]

ANDERSSON, G., ENGEBRETSEN, L., AND H~STAD, J. 1999. A new way to use semidefinite programming with applications to linear equations mod p. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms Baltimore, Md., Jan. 17-19. ACM New York, pp. 41-50.

Digital Library

[3]

ARORA, S., LUND, C., MOTWANI, R., SUDAN, M., AND SZEGEDY, M. 1998. Proof verification and intractability of approximation problems. J. ACM 45, 3 (May), 501-555.

Digital Library

[4]

ARORA, S., AND SAFRA, S. 1998. Probabilistic checking of proofs: a new characterization of NP. J. ACM 45, 1 (Jan.) 70-122.

Digital Library

[5]

BABAI, L., FORTNOW, L., LEVIN, L., AND SZEGEDY, M. 1991b Checking computations in polylogarithmic time. In Proceedings of the 23rd Annual Symposium on the Theory of Computation (New Orleans, La., May 6-8). ACM, New York, pp. 21-31.

Digital Library

[6]

BABAI, L., FORTNOW, L., AND LUND, C. 1991a Non-deterministic exponential time has two-prover interactive protocols. Computat. Compl. 1, 3-40.

[7]

BAR-YEHUDA, R., AND EVEN, S. 1981. A linear time approximation algorithm for the weighted vertex cover algorithm. J. Algorithms 2, 198-210.

[8]

BELLARE, M., COPPERSMITH, D., H~STAD, J., KIWI, M., AND SUDAN, M. 1996. Linearity testing in characteristic two. IEEE Trans. Inf. Theory 42, 6 (Nov.), 1781-1796.

[9]

BELLARE, M., GOLDREICH, O., AND SUDAN, M. 1998. Free Bits, PCPs and Non-Approximability- Towards tight Results. SIAM J. Comput. 27, 804-915.

Digital Library

[10]

BELLARE, M., GOLDWASSER, S., LUND, C., AND RUSSELL, A. 1993. Efficient probabilistically checkable proofs and applications to approximation. In Proceedings of the 25th Annual ACMSymposium on Theory of Computation (San Diego, Calif., May 16-18). ACM, New York, pp. 294-304. (See also Errata sheet in Proceedings of the 26th Annual ACM Symposium on Theory of Computation (Montreal, Que., Canada). ACM, New York, p. 820).

Digital Library

[11]

BELLARE, M., AND SUDAN, M. 1994. Improved non-approximability results. In Proceedings of 26th Annual ACM Symposium on Theory of Computation (Montreal, Que., Canada, May 23-25). ACM, New York, pp. 184-193.

Digital Library

[12]

BEN-OR, M., GOLDWASSER, S., KILIAN, J., AND WIGDERSON, A. 1998. Multiprover interactive proofs: How to remove intractability. In Proceedings of the 20th Annual ACM Symposium on Theory of Computation (Chicago, Ill., May 2-4). ACM, New York, pp. 113-131.

Digital Library

[13]

BLUM, M., LUBY, M., AND RUBINFELD, R. 1993. Self-testing/ correcting with applications to numerical problems. J. Comput. Sys. Sci. 47, 549-595.

Digital Library

[14]

FEIGE, U. 1998. A threshold of ln n for approximating set cover. J. ACM, 45, 634-652.

Digital Library

[15]

FEIGE, U., AND GOEMANS, M. 1995. Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT. In Proceedings of the 3rd Israeli Symposium on the theory of Computing and Systems. IEEE Computer Society, Tel Aviv, Israel, pp. 182-189.

Digital Library

[16]

FEIGE, U., GOLDWASSER, S., LOVASZ L., SAFRA S., AND SZEGEDY, M. 1996. Interactive proofs and the hardness of approximating cliques. J. ACM, 43, 2 (Mar.), 268-292.

Digital Library

[17]

FEIGE, U., AND KILIAN, J. 1998. Zero-knowledge and the chromatic number. J. Comput. Syst. Sci. 57,2, 187-200.

Digital Library

[18]

FORTNOW, L., ROMPEL, J., AND SIPSER, M. 1994. On the power of multi-prover interactive protocols. Theoret. Comput. Sci. 134, 2, 545-557.

Digital Library

[19]

GAREY,M.R.,AND JOHNSON, D. S. 1979. Computers and Intractability. W. H. Freeman and Company, New York.

Digital Library

[20]

GOEMANS, M., AND WILLIAMSON, D. 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 6, 1115-1145.

Digital Library

[21]

GURUSWAMI, V., LEWIN, D., SUDAN, M., AND TREVISAN, L. 1998. A tight characterization of NP with 3 query PCPs. In Proceedings of 39th Annual IEEE Symposium on Foundations of Computer Science (Palo Alto, Calif.). IEEE Computer Society Press, Los Alamitos, Calif., pp. 8-17.

Digital Library

[22]

HASTAD, J. 1999. Clique is hard to approximate within n1Acta Math. 182, 105-142.

[23]

HOCHBAUM, D. 1983. Efficient algorithms for the stable set, vertex cover and set packing problems. Disc. Appl. Math. 6, 243-254.

[24]

JOHNSON, D.S. 1974. Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci 9, 256-278.

Digital Library

[25]

JUDSON, T. 1994. Abstract Algebra, Theory and Applications. PWS Publishing Company, Boston, Mass.

[26]

KANN, V., LAGERGREN, J., AND PANCONESI, A. 1996. Approximability of maximum splitting of k-sets and some other APX-complete problems. Inf. proc. lett. 58, 105-110.

Digital Library

[27]

LUND, C., FORTNOW, L., KARLOFF, H., AND NISAN, N. Algebraic methods for interactive proof systems. J. ACM 39, 2 (Apr.), 859-868.

Digital Library

[28]

PAPADIMITRIOU, C., AND YANNAKAKIS, M. 1991. Optimization, approximation and complexity classes. J. Comput. Syst. Sci. 43, pp. 425-440.

[29]

RAZ, R. 1998. A parallel repetition theorem. SIAM J. Comput, 27, 3, 763-803.

Digital Library

[30]

SHAMIR, A. 1992. IP D PSPACE. J. ACM 39, 2 (Apr.) 869-877.

Digital Library

[31]

TREVISAN, L., SORKIN, G., SUDAN, M., AND WILLIAMSON, D. 2000. Gadgets, approximation and linear programming. SIAM J. Comput. 29, 2074-2097.

Digital Library

[32]

ZWICK, U. 1998. Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, Calif., Jan). ACM, New York, pp. 201-210.

Digital Library

Cited By

Díez-Valle PPorras DGarcía-Ripoll J(2024)Connection between single-layer quantum approximate optimization algorithm interferometry and thermal distribution samplingFrontiers in Quantum Science and Technology10.3389/frqst.2024.13212643Online publication date: 14-Feb-2024
https://doi.org/10.3389/frqst.2024.1321264
Sinjorgo LSotirov R(2024)On Solving MAX-SAT Using Sum of SquaresINFORMS Journal on Computing10.1287/ijoc.2023.003636:2(417-433)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1287/ijoc.2023.0036
Lubinski TCoffrin CMcGeoch CSathe PApanavicius JBernal Neira DQuantum Economic Development Consortium(QED-C) Collaboration (2024)Optimization Applications as Quantum Performance BenchmarksACM Transactions on Quantum Computing10.1145/36781845:3(1-44)Online publication date: 14-Aug-2024
https://dl.acm.org/doi/10.1145/3678184
Show More Cited By

Index Terms

Some optimal inapproximability results
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Approximation resistance from pairwise independent subgroups
STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

We show optimal (up to constant factor) NP-hardness for Max-k-CSP over any domain, whenever k is larger than the domain size. This follows from our main result concerning predicates over abelian groups. We show that a predicate is approximation ...
Reductions, codes, PCPs, and inapproximability
FOCS '95: Proceedings of the 36th Annual Symposium on Foundations of Computer Science

Many recent results show the hardness of approximating NP-hard functions. We formalize, in a very simple way, what these results involve: a code-like Levin reduction. Assuming a well-known complexity assumption, we show that such reductions cannot prove ...
Inapproximability results for equations over infinite groups

An equation over a group G is an expression of form w"1...w"k=1"G, where each w"i is either a variable, an inverted variable, or a group constant and 1"G denotes the identity element; such an equation is satisfiable if there is a setting of the ...

Comments

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 48, Issue 4

July 2001

303 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/502090

Issue’s Table of Contents

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2001

Published in JACM Volume 48, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

994
Total Citations
View Citations
5,213
Total Downloads

Downloads (Last 12 months)232
Downloads (Last 6 weeks)10

Reflects downloads up to 03 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Díez-Valle PPorras DGarcía-Ripoll J(2024)Connection between single-layer quantum approximate optimization algorithm interferometry and thermal distribution samplingFrontiers in Quantum Science and Technology10.3389/frqst.2024.13212643Online publication date: 14-Feb-2024
https://doi.org/10.3389/frqst.2024.1321264
Sinjorgo LSotirov R(2024)On Solving MAX-SAT Using Sum of SquaresINFORMS Journal on Computing10.1287/ijoc.2023.003636:2(417-433)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1287/ijoc.2023.0036
Lubinski TCoffrin CMcGeoch CSathe PApanavicius JBernal Neira DQuantum Economic Development Consortium(QED-C) Collaboration (2024)Optimization Applications as Quantum Performance BenchmarksACM Transactions on Quantum Computing10.1145/36781845:3(1-44)Online publication date: 14-Aug-2024
https://dl.acm.org/doi/10.1145/3678184
Barto LButti SKazda AViola CŽivný SSobocinski PLago UEsparza J(2024)Algebraic Approach to ApproximationProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662076(1-14)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662076
Ron-Zewi NRothblum R(2024)Local Proofs Approaching the Witness LengthJournal of the ACM10.1145/366148371:3(1-42)Online publication date: 25-Apr-2024
https://dl.acm.org/doi/10.1145/3661483
Chou CGolovnev ASudan MVelusamy S(2024)Sketching Approximability of All Finite CSPsJournal of the ACM10.1145/364943571:2(1-74)Online publication date: 12-Apr-2024
https://dl.acm.org/doi/10.1145/3649435
Cao NCohen-Addad VLee ELi SNewman AVogl LMohar BShinkar IO'Donnell R(2024)Understanding the Cluster Linear Program for Correlation ClusteringProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649749(1605-1616)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649749
Ciardo LŽivný SMohar BShinkar IO'Donnell R(2024)Semidefinite Programming and Linear Equations vs. Homomorphism ProblemsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649635(1935-1943)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649635
Buchbinder NFeldman MMohar BShinkar IO'Donnell R(2024)Constrained Submodular Maximization via New Bounds for DR-Submodular FunctionsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649630(1820-1831)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649630
Minzer DZheng KMohar BShinkar IO'Donnell R(2024)Near Optimal Alphabet-Soundness Tradeoff PCPsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649606(15-23)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649606
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents