Article

Free access

A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction

Authors:

Sanjeev Khanna,

Madhu Sudan,

David P. WilliamsonAuthors Info & Claims

STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing

Pages 11 - 20

https://doi.org/10.1145/258533.258538

Published: 04 May 1997 Publication History

PDF eReader

References

[1]

S. ARORA, C. LUND, R. MOTWANI, M. SUDAN, AND M. SZEGEDY. Proof verification and the intractability of approximation problems. Proceedings of the 33rd IEEE FOC$, IEEE, 1992.

Google Scholar

[2]

T. ASANO, T. ONO, AND T. HmATA. Approximarion algorithms for the maximum satisfiability problem. ScandanaWan Workshop on Algorithmic Theory 96 Proceedings, Lecture Notes in Computer Science Vol. 1097, ed., Springer-Verlag, 1996.

Digital Library

Google Scholar

[3]

M. BELLARE, O. GOLDREICH, AND M. SUDAN. Free bits, PCP and non-approximability- towards tight results. (Version 3). ECCC Technical Report number TR95-024, 1995.

Google Scholar

[4]

N. CREIGNOU. A Dichotomy Theorem for Maximum Generalized Satisfiability Problems. Journal of Computer and System Sciences, 51:3, pp. 511- 522, 1995.

Digital Library

Google Scholar

[5]

T. FEDER AND M. VARDI. Monotone monadic SNP and constraint satisfaction. Proceedings of the 25th ACM STOC, ACM, 1993.

Digital Library

Google Scholar

[6]

M. GOEMANS AND D. WILLIAMSON. New 3/4- approximation algorithms for MAX SAT. SIAM Journal on Discrete Mathematics, 7:656-666, 1994.

Digital Library

Google Scholar

[7]

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

Digital Library

Google Scholar

[8]

S. KHANNA AND R. MOTWANI. Towards a Syntactic Characterization of PTAS, pp. 329-337. Proceedings of the 28th ACM STOC, ACM, 1996.

Digital Library

Google Scholar

[9]

S. KHANNA, R. MOTWANI, M. SUDAN, AND U. VAZIRANI. On Syntactic versus Computational Views of Approximation. Proceedings of the 35th IEEE FOCS, IEEE, 1994, pp. 819-830.

Google Scholar

[10]

S. KHANNA, M. SUDAN, AND D.P. WILLIAMSON. A complete classification of the approximability of maximization problems derived from boolean constraint satisfaction. Electonic Colloquium on Computational Complezity, Technical report no. TR96- 062, 1996.

Google Scholar

[11]

S. KHANNA, M. SUDAN AND L. TREVISAN. Constraint Satisfaction: The Approximability of Minimization Problems. To appear in the Proceedings of the 12th Annual IEEE Computational Complezi~y Conference (CCC), 1997.

Digital Library

Google Scholar

[12]

R. LADNSR. On the structure of polynomial time reducibility. Journal of the A CM, 22:1, pp. 155- 171, 1975.

Digital Library

Google Scholar

[13]

C. LUND AND M. YANNAKAKIS. The approximation of maximum subgraph problems. In Proceedings of International Colloquium on Automata, Languages and Programming, ICALP, pp. 40-51, 1993.

Digital Library

Google Scholar

[14]

W. MmaKI, l~. Structural properties of bounded relations with an application to NP optimization problems. Technical Report, Mathematical Institute, University of Heidelberg, (http://math.uni-heidelberg.de/logic/), December 1996.

Google Scholar

[15]

C. PAPADIMITRIOU. Computational Complezity. Addison Wesley Publishing Company, 1994.

Google Scholar

[16]

C. PAPADIMITRIOU AND M. YANNAKAKIS. Optimization, approximation and complexity classes. Journal of Computer and System Sciences, 43, pp. 425-440, 1991.

Crossref

Google Scholar

[17]

T. SCHAEFER. The complexity of satisfiability problems Proceedings of the 10th ACM STOC, ACM, 1978.

Digital Library

Google Scholar

[18]

L. TREVlSAN, G. SORKIN, M. SUDAN AND D. WILLIAMSON. Gadgets, approximation and linear programming. Proceedings of the 37th iEEE FOCS, IEEE, 1996.

Digital Library

Google Scholar

[19]

M. YANNAKAKIS, On the approximation of maximum satisfiability. Journal of Algorithms, vol. 17, pages 475-502, 1994.

Digital Library

Google Scholar

Cited By

View all

Dell HKim ELampis MMitsou VMömke T(2017)Complexity and Approximability of Parameterized MAX-CSPsAlgorithmica10.1007/s00453-017-0310-879:1(230-250)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1007/s00453-017-0310-8
Schmidt J(2017)The Weight in EnumerationLanguage and Automata Theory and Applications10.1007/978-3-319-53733-7_15(208-219)Online publication date: 16-Feb-2017
https://doi.org/10.1007/978-3-319-53733-7_15
Cubitt TMontanaro A(2014)Complexity Classification of Local Hamiltonian ProblemsProceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science10.1109/FOCS.2014.21(120-129)Online publication date: 18-Oct-2014
https://dl.acm.org/doi/10.1109/FOCS.2014.21
Show More Cited By

Index Terms

A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction

Recommendations

The Approximability of Constraint Satisfaction Problems

We study optimization problems that may be expressed as "Boolean constraint satisfaction problems." An instance of a Boolean constraint satisfaction problem is given by m constraints applied to n Boolean variables. Different computational problems arise ...
Optimization, randomized approximability, and boolean constraint satisfaction problems
ISAAC'11: Proceedings of the 22nd international conference on Algorithms and Computation

We give a unified treatment to optimization problems that can be expressed in the form of nonnegative-real-weighted Boolean constraint satisfaction problems. Creignou, Khanna, Sudan, Trevisan, and Williamson studied the complexity of approximating their ...
Approximate counting for complex-weighted Boolean constraint satisfaction problems

Constraint satisfaction problems (or CSPs) have been extensively studied in, for instance, artificial intelligence, database theory, graph theory, and statistical physics. From a practical viewpoint, it is beneficial to approximately solve those CSPs. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing

May 1997

752 pages

ISBN:0897918886

DOI:10.1145/258533

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: 04 May 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC97

Sponsor:

SIGACT

STOC97: 29th Annual Symposium on Theory of Computing

May 4 - 6, 1997

Texas, El Paso, USA

Acceptance Rates

STOC '97 Paper Acceptance Rate 75 of 211 submissions, 36%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

47
Total Citations
View Citations
585
Total Downloads

Downloads (Last 12 months)95
Downloads (Last 6 weeks)13

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Dell HKim ELampis MMitsou VMömke T(2017)Complexity and Approximability of Parameterized MAX-CSPsAlgorithmica10.1007/s00453-017-0310-879:1(230-250)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1007/s00453-017-0310-8
Schmidt J(2017)The Weight in EnumerationLanguage and Automata Theory and Applications10.1007/978-3-319-53733-7_15(208-219)Online publication date: 16-Feb-2017
https://doi.org/10.1007/978-3-319-53733-7_15
Cubitt TMontanaro A(2014)Complexity Classification of Local Hamiltonian ProblemsProceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science10.1109/FOCS.2014.21(120-129)Online publication date: 18-Oct-2014
https://dl.acm.org/doi/10.1109/FOCS.2014.21
Bazgan C(2013)Optimal SatisfiabilityParadigms of Combinatorial Optimization10.1002/9781118600207.ch1(1-31)Online publication date: 13-Feb-2013
https://doi.org/10.1002/9781118600207.ch1
Creignou NOlive FSchmidt J(2011)Enumerating all solutions of a boolean CSP by non-decreasing weightProceedings of the 14th international conference on Theory and application of satisfiability testing10.5555/2023474.2023489(120-133)Online publication date: 19-Jun-2011
https://dl.acm.org/doi/10.5555/2023474.2023489
Bhalgat AChakraborty TKhanna SParkes DDellarocas CTennenholtz M(2010)Approximating pure nash equilibrium in cut, party affiliation, and satisfiability gamesProceedings of the 11th ACM conference on Electronic commerce10.1145/1807342.1807353(73-82)Online publication date: 7-Jun-2010
https://dl.acm.org/doi/10.1145/1807342.1807353
Creignou NVollmer H(2008)Boolean Constraint Satisfaction ProblemsComplexity of Constraints10.1007/978-3-540-92800-3_2(3-37)Online publication date: 23-Dec-2008
https://dl.acm.org/doi/10.1007/978-3-540-92800-3_2
Halldórsson MKratochvíl JTelle J(2006)Independent sets with domination constraintsAutomata, Languages and Programming10.1007/BFb0055051(176-187)Online publication date: 26-May-2006
https://doi.org/10.1007/BFb0055051
Serna MTrevisan LXhafa F(2005)The (parallel) approximability of non-boolean satisfiability problems and restricted integer programmingSTACS 9810.1007/BFb0028584(488-498)Online publication date: 20-Jun-2005
https://doi.org/10.1007/BFb0028584
Nešetřil JTurzí'k D(2005)Solving and approximating combinatorial optimization problems (Towards MAX CUT and TSP)SOFSEM'97: Theory and Practice of Informatics10.1007/3-540-63774-5_98(70-85)Online publication date: 29-Jul-2005
https://doi.org/10.1007/3-540-63774-5_98
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

The Approximability of Constraint Satisfaction Problems

Optimization, randomized approximability, and boolean constraint satisfaction problems

Approximate counting for complex-weighted Boolean constraint satisfaction problems