TY - GEN
T1 - A new algorithm for MAX-2-SAT
AU - Hirsch, Edward A.
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.
PY - 2000
Y1 - 2000
N2 - Recently there was a significant progress in proving (exponential- time) worst-case upper bounds for the propositional satisfiability problem (SAT) and related problems. In particular, for MAX-2-SAT Niedermeier and Rossmanith recently presented an algorithm with worstcase upper bound O(K·2K/2:88…), and the bound O(K·2K/3:44..) is implicit from the paper by Bansal and Raman (K is the number of clauses). In this paper we improve this bound to p(K)2K2/4, where K2 is the number of 2-clauses, and p is a polynomial. In addition, our algorithm and the proof are much simpler than the previous ones. The key ideas are to use the symmetric flow algorithm of Yannakakis and to count only 2-clauses (and not 1-clauses).
AB - Recently there was a significant progress in proving (exponential- time) worst-case upper bounds for the propositional satisfiability problem (SAT) and related problems. In particular, for MAX-2-SAT Niedermeier and Rossmanith recently presented an algorithm with worstcase upper bound O(K·2K/2:88…), and the bound O(K·2K/3:44..) is implicit from the paper by Bansal and Raman (K is the number of clauses). In this paper we improve this bound to p(K)2K2/4, where K2 is the number of 2-clauses, and p is a polynomial. In addition, our algorithm and the proof are much simpler than the previous ones. The key ideas are to use the symmetric flow algorithm of Yannakakis and to count only 2-clauses (and not 1-clauses).
UR - http://www.scopus.com/inward/record.url?scp=84944062558&partnerID=8YFLogxK
U2 - 10.1007/3-540-46541-3_5
DO - 10.1007/3-540-46541-3_5
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:84944062558
SN - 9783540671411
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 65
EP - 73
BT - STACS 2000 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, Proceedings
A2 - Reichel, Horst
A2 - Tison, Sophie
T2 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000
Y2 - 17 February 2000 through 19 February 2000
ER -