Article

Balanced max 2-sat might not be the hardest

Author:

Per AustrinAuthors Info & Claims

STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

Pages 189 - 197

https://doi.org/10.1145/1250790.1250818

Published: 11 June 2007 Publication History

Abstract

We show that, assuming the Unique Games Conjecture, it is NP-hard to approximate MAX2SAT within α_LLZ^-+ε, where 0.9401 < α_LLZ^- < 0.9402 is the believed approximation ratio of the algorithm of Lewin, Livnat and Zwick [28].

This result is surprising considering the fact that balanced instances of MAX2SAT, i.e., instances where each variable occurs positively and negatively equally often, can be approximated within 0.9439. In particular, instances in which roughly 68% of the literals are unnegated variables and 32% are negated appear less amenable to approximation than instances where the ratio is 50% - 50%.

References

[1]

F. Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization, 5:13--51, 1995.

Digital Library

[2]

S. Arora, E. Chlamtac, and M. Charikar. New Approximation Guarantee for Chromatic Number. In STOC 2006, pages 205--214, 2006.

Digital Library

[3]

S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof Verification and the Hardness of Approximation Problems. Journal of the ACM, 45(3):501--555, 1998.

Digital Library

[4]

S. Arora and S. Safra. Probabilistic Checking of Proofs: A New Characterization of NP. Journal of the ACM, 45(1):70--122, 1998.

Digital Library

[5]

P. Austrin. Balanced Max 2-Sat might not be the hardest. Technical report, Electronic Colloquium on Computational Complexity Report TR06-088, 2006.

[6]

A. Blum and D. Karger. An Õ(n^3/14)-coloring algorithm for 3-colorable graphs. Information Processing Letters, 61(1):49--53, 1997.

Digital Library

[7]

M. Charikar, K. Makarychev, and Y. Makarychev. Approximation Algorithm for the Max k-CSP Problem, 2006.

[8]

M. Charikar, K. Makarychev, and Y. Makarychev. Near-optimal algorithms for unique games. In STOC 2006, pages 205--214, 2006.

Digital Library

[9]

M. Charikar and A. Wirth. Maximizing Quadratic Programs: Extending Grothendieck's Inequality. In FOCS 2004, pages 54--60, 2004.

Digital Library

[10]

S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar. On the hardness of approximating multicut and sparsest-cut. In 20th Annual IEEE Conference on Computational Complexity, pages 144--153, June 2005.

Digital Library

[11]

P. Crescenzi, R. Silvestri, and L. Trevisan. On Weighted vs Unweighted Versions of Combinatorial Optimization Problems. Information and Computation, 167(1):10--26, 2001.

Digital Library

[12]

I. Dinur, E. Mossel, and O. Regev. Conditional hardness for approximate coloring. In STOC 2006, pages 344--353, 2006.

Digital Library

[13]

U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634--652, 1998.

Digital Library

[14]

U. Feige and M. Goemans. Aproximating the Value of Two Prover Proof Systems, With Applications to MAX 2SAT and MAX DICUT. In ISTCS 1995, pages 182--189, 1995.

Digital Library

[15]

U. Feige and J. Kilian. Zero Knowledge and the Chromatic Number. Journal of Computer and System Sciences, 57(2):187--199, 1998.

Digital Library

[16]

M.X. Goemans and D.P. Williamson. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. Journal of the ACM, 42:1115--1145, 1995.

Digital Library

[17]

E. Halperin, R. Nathaniel, and U. Zwick. Coloring k-colorable graphs using smaller palettes. In SODA 2001, pages 319--326, 2001.

Digital Library

[18]

G. Hast. Approximating Max kCSP -- Outperforming a Random Assignment with Almost a Linear Factor. In ICALP 2005, pages 956--968, 2005.

Digital Library

[19]

J. Håstad. Clique is hard to approximate within n^1-ε. Acta Mathematica, 48(4):105--142, 1999.

[20]

J. Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798--859, 2001.

Digital Library

[21]

J. Håstad. On the approximation resistance of a random predicate. Manuscript, 2006.

[22]

D.R. Karger, R. Motwani, and M. Sudan. Approximate graph coloring by semidefinite programming. Journal of the ACM, 45(2):246--265, 1998.

Digital Library

[23]

S. Khot. On the power of unique 2-prover 1-round games. In STOC 2002, pages 767--775, 2002.

Digital Library

[24]

S. Khot, G. Kindler, E. Mossel, and R. O'Donnell. Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs? In FOCS 2004, pages 146--154. IEEE Computer Society, 2004.

Digital Library

[25]

S. Khot and R. O'Donnell. SDP gaps and UGC-hardness for MAXCUTGAIN. In FOCS, pages 217--226. IEEE Computer Society, 2006.

Digital Library

[26]

S. Khot and O. Regev. Vertex Cover Might be Hard to Approximate to within 2-ε. In IEEE Conference on Computational Complexity, pages 379--. IEEE Computer Society, 2003.

[27]

S. Khot and N.K. Vishnoi. The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l₁. In FOCS 2005, pages 53--62, 2005.

Digital Library

[28]

M. Lewin, D. Livnat, and U. Zwick. Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems. In IPCO 2002, volume 2337 of Lecture Notes in Computer Science, pages 67--82, 2002.

Digital Library

[29]

S. Matuura and T. Matsui. 0.863-approximation algorithm for max dicut. In RANDOM-APPROX, pages 138--146, 2001.

Digital Library

[30]

S. Matuura and T. Matsui. 0.935-Approximation Randomized Algorithm for MAX 2SAT and Its Derandomization. Technical Report METR 2001-03, Department of Mathematical Engineering and Information Physics, the University of Tokyo, Japan, 2001.

[31]

E. Mossel, R. O'Donnell, and K. Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality. Preprint, 2005.

Digital Library

[32]

A. Samorodnitsky and L. Trevisan. Gowers uniformity, influence of variables, and PCPs. In STOC 2006, pages 11--20, 2006.

Digital Library

[33]

U. Zwick. Personal communication, 2005.

Cited By

Brakensiek JHuang NPotechin AZwick U(2023)Separating MAX 2-AND, MAX DI-CUT and MAX CUT2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00023(234-252)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00023
Stanković A(2022)On regularity of Max-CSPs and Min-CSPsInformation Processing Letters10.1016/j.ipl.2022.106244(106244)Online publication date: Jan-2022
https://doi.org/10.1016/j.ipl.2022.106244
Brakensiek JHuang NPotechin AZwick UMarx D(2021)On the mysteries of MAX NAE-SATProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458094(484-503)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458094
Show More Cited By

Index Terms

Balanced max 2-sat might not be the hardest
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Complexity of approximating CSP with balance / hard constraints
ITCS '14: Proceedings of the 5th conference on Innovations in theoretical computer science

We study two natural extensions of Constraint Satisfaction Problems (CSPs). Balance-Max-CSP requires that in any feasible assignment each element in the domain is used an equal number of times. An instance of Hard-Max-CSP consists of soft constraints ...
Vertex cover might be hard to approximate to within 2-ε

Based on a conjecture regarding the power of unique 2-prover-1-round games presented in [S. Khot, On the power of unique 2-Prover 1-Round games, in: Proc. 34th ACM Symp. on Theory of Computing, STOC, May 2002, pp. 767-775], we show that vertex cover is ...
On the max min vertex cover problem

We address the max min vertex cover problem, which is the maximization version of the well studied min independent dominating set problem, known to be NP -hard and highly inapproximable in polynomial time. We present tight approximation results for this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

June 2007

734 pages

ISBN:9781595936318

DOI:10.1145/1250790

General Chair:
David Johnson
AT&T Labs - Research
,
Program Chair:
Uriel Feige
Microsoft Research and Weizmann Institute

Copyright © 2007 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC07

Sponsor:

STOC07: Symposium on Theory of Computing

June 11 - 13, 2007

California, San Diego, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
428
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)2

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Brakensiek JHuang NPotechin AZwick U(2023)Separating MAX 2-AND, MAX DI-CUT and MAX CUT2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00023(234-252)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00023
Stanković A(2022)On regularity of Max-CSPs and Min-CSPsInformation Processing Letters10.1016/j.ipl.2022.106244(106244)Online publication date: Jan-2022
https://doi.org/10.1016/j.ipl.2022.106244
Brakensiek JHuang NPotechin AZwick UMarx D(2021)On the mysteries of MAX NAE-SATProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458094(484-503)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458094
Austrin PBrown-Cohen JHåstad JMarx D(2021)Optimal inapproximability with universal factor graphsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458091(434-453)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458091
Larsson JMarkström K(2021) Biased random k ‐SAT Random Structures & Algorithms10.1002/rsa.2099659:2(238-266)Online publication date: 16-Feb-2021
https://doi.org/10.1002/rsa.20996
Liu ZTian F(2016)Improved approximating $2$-CatSP for $\sigma\geq 0.50$ with an unbalanced rounding matrixJournal of Industrial and Management Optimization10.3934/jimo.2016.12.124912:4(1249-1265)Online publication date: Jan-2016
https://doi.org/10.3934/jimo.2016.12.1249
Austrin PBenabbas SGeorgiou K(2016)Better Balance by Being BiasedACM Transactions on Algorithms10.1145/290705213:1(1-27)Online publication date: 10-Oct-2016
https://dl.acm.org/doi/10.1145/2907052
Paul APoloczek MWilliamson D(2016)Simple Approximation Algorithms for Balanced MAX 2SATLATIN 2016: Theoretical Informatics10.1007/978-3-662-49529-2_49(659-671)Online publication date: 22-Mar-2016
https://doi.org/10.1007/978-3-662-49529-2_49
Austrin PBenabbas SGeorgiou KKhanna S(2013)Better balance by being biasedProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627838(277-294)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627838
Mikhailyuk V(2013)Optimal Approximation Algorithms for Reoptimization of Constraint Satisfaction ProblemsAmerican Journal of Operations Research10.4236/ajor.2013.3202503:02(279-288)Online publication date: 2013
https://doi.org/10.4236/ajor.2013.32025
Show More Cited By

View Options

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents