Balanced Max 2-Sat Might Not be the Hardest: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING
2007 (English)In: STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, New York: ASSOC COMPUTING MACHINERY, , 2007, 189-197 p.Conference paper (Refereed)
We show that, assuming the Unique Games Conjecture, it is NP-hard to approximate MAX 2-SAT within alpha(-)(L)(LZ)+epsilon where 0.9401 < alpha(-)(L)(LZ) < 0.9402 is the believed approximation ratio of the algorithm of Lewin, Livnat and Zwick .. This result is surprising considering the fact that balanced instances of MAX 2-SAT, 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%.
Place, publisher, year, edition, pages
New York: ASSOC COMPUTING MACHINERY, , 2007. 189-197 p.
, Annual ACM Symposium on Theory of Computing, ISSN 0737-8017
Max 2-Sat, Unique Games Conjecture, Inapproximability
IdentifiersURN: urn:nbn:se:kth:diva-30814DOI: 10.1145/1250790.1250818ISI: 000267050000021ScopusID: 2-s2.0-35448957666ISBN: 978-1-59593-631-8OAI: oai:DiVA.org:kth-30814DiVA: diva2:403193
39th Annual ACM Symposium on Theory of Computing San Diego, CA, JUN 11-13, 2007
QC 201103112011-03-112011-03-042016-06-20Bibliographically approved