Standard

A new algorithm for MAX-2-SAT. / Hirsch, Edward A.

STACS 2000 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, Proceedings. ed. / Horst Reichel; Sophie Tison. Springer Nature, 2000. p. 65-73 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1770).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Harvard

Hirsch, EA 2000, A new algorithm for MAX-2-SAT. in H Reichel & S Tison (eds), STACS 2000 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1770, Springer Nature, pp. 65-73, 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, Lille, France, 17/02/00.

APA

Hirsch, E. A. (2000). A new algorithm for MAX-2-SAT. In H. Reichel, & S. Tison (Eds.), STACS 2000 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, Proceedings (pp. 65-73). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1770). Springer Nature.

Vancouver

Hirsch EA. A new algorithm for MAX-2-SAT. In Reichel H, Tison S, editors, STACS 2000 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, Proceedings. Springer Nature. 2000. p. 65-73. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

Author

Hirsch, Edward A. / A new algorithm for MAX-2-SAT. STACS 2000 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, Proceedings. editor / Horst Reichel ; Sophie Tison. Springer Nature, 2000. pp. 65-73 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{b97b65a6b6de412e8b71565ddde7acc6,
title = "A new algorithm for MAX-2-SAT",
abstract = "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).",
author = "Hirsch, {Edward A.}",
year = "2000",
month = jan,
day = "1",
language = "English",
isbn = "9783540671411",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "65--73",
editor = "Horst Reichel and Sophie Tison",
booktitle = "STACS 2000 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, Proceedings",
address = "Germany",
note = "17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000 ; Conference date: 17-02-2000 Through 19-02-2000",

}

RIS

TY - GEN

T1 - A new algorithm for MAX-2-SAT

AU - Hirsch, Edward A.

PY - 2000/1/1

Y1 - 2000/1/1

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

M3 - Conference contribution

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

PB - Springer Nature

T2 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000

Y2 - 17 February 2000 through 19 February 2000

ER -

ID: 49829759