Per Austrin
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%.
- F. Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization, 5:13--51, 1995.Google Scholar
Digital Library
- S. Arora, E. Chlamtac, and M. Charikar. New Approximation Guarantee for Chromatic Number. In STOC 2006, pages 205--214, 2006. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- S. Arora and S. Safra. Probabilistic Checking of Proofs: A New Characterization of NP. Journal of the ACM, 45(1):70--122, 1998. Google ScholarDigital Library
- P. Austrin. Balanced Max 2-Sat might not be the hardest. Technical report, Electronic Colloquium on Computational Complexity Report TR06-088, 2006.Google Scholar
- A. Blum and D. Karger. An Õ(n3/14)-coloring algorithm for 3-colorable graphs. Information Processing Letters, 61(1):49--53, 1997. Google ScholarDigital Library
- M. Charikar, K. Makarychev, and Y. Makarychev. Approximation Algorithm for the Max k-CSP Problem, 2006.Google Scholar
- M. Charikar, K. Makarychev, and Y. Makarychev. Near-optimal algorithms for unique games. In STOC 2006, pages 205--214, 2006. Google ScholarDigital Library
- M. Charikar and A. Wirth. Maximizing Quadratic Programs: Extending Grothendieck's Inequality. In FOCS 2004, pages 54--60, 2004. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- P. Crescenzi, R. Silvestri, and L. Trevisan. On Weighted vs Unweighted Versions of Combinatorial Optimization Problems. Information and Computation, 167(1):10--26, 2001. Google ScholarDigital Library
- I. Dinur, E. Mossel, and O. Regev. Conditional hardness for approximate coloring. In STOC 2006, pages 344--353, 2006. Google ScholarDigital Library
- U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634--652, 1998. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- U. Feige and J. Kilian. Zero Knowledge and the Chromatic Number. Journal of Computer and System Sciences, 57(2):187--199, 1998. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- E. Halperin, R. Nathaniel, and U. Zwick. Coloring k-colorable graphs using smaller palettes. In SODA 2001, pages 319--326, 2001. Google ScholarDigital Library
- G. Hast. Approximating Max kCSP -- Outperforming a Random Assignment with Almost a Linear Factor. In ICALP 2005, pages 956--968, 2005. Google ScholarDigital Library
- J. Håstad. Clique is hard to approximate within n1-ε. Acta Mathematica, 48(4):105--142, 1999.Google ScholarCross Ref
- J. Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798--859, 2001. Google ScholarDigital Library
- J. Håstad. On the approximation resistance of a random predicate. Manuscript, 2006.Google Scholar
- D.R. Karger, R. Motwani, and M. Sudan. Approximate graph coloring by semidefinite programming. Journal of the ACM, 45(2):246--265, 1998. Google ScholarDigital Library
- S. Khot. On the power of unique 2-prover 1-round games. In STOC 2002, pages 767--775, 2002. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- S. Khot and R. O'Donnell. SDP gaps and UGC-hardness for MAXCUTGAIN. In FOCS, pages 217--226. IEEE Computer Society, 2006. Google ScholarDigital Library
- 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.Google Scholar
- S. Khot and N.K. Vishnoi. The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l1. In FOCS 2005, pages 53--62, 2005. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- S. Matuura and T. Matsui. 0.863-approximation algorithm for max dicut. In RANDOM-APPROX, pages 138--146, 2001. Google ScholarDigital Library
- 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.Google Scholar
- E. Mossel, R. O'Donnell, and K. Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality. Preprint, 2005. Google ScholarDigital Library
- A. Samorodnitsky and L. Trevisan. Gowers uniformity, influence of variables, and PCPs. In STOC 2006, pages 11--20, 2006. Google ScholarDigital Library
- U. Zwick. Personal communication, 2005.Google Scholar
Index Terms
- Balanced max 2-sat might not be the hardest
Recommendations
Complexity of approximating CSP with balance / hard constraints
ITCS '14: Proceedings of the 5th conference on Innovations in theoretical computer scienceWe 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