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. ред. / Horst Reichel; Sophie Tison. Springer Nature, 2000. стр. 65-73 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 1770).
Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование
Harvard
Hirsch, EA 2000,
A new algorithm for MAX-2-SAT. в H Reichel & S Tison (ред.),
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), Том. 1770, Springer Nature, стр. 65-73, 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, Lille, Франция,
17/02/00.
APA
Hirsch, E. A. (2000).
A new algorithm for MAX-2-SAT. в H. Reichel, & S. Tison (Ред.),
STACS 2000 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, Proceedings (стр. 65-73). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 1770). Springer Nature.
Vancouver
Hirsch EA.
A new algorithm for MAX-2-SAT. в Reichel H, Tison S, Редакторы, STACS 2000 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, Proceedings. Springer Nature. 2000. стр. 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. Редактор / Horst Reichel ; Sophie Tison. Springer Nature, 2000. стр. 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 -
