A new algorithm for MAX-2-SAT

Research outputpeer-review

25 Citations (Scopus)

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).

Original languageEnglish
Title of host publicationSTACS 2000 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, Proceedings
EditorsHorst Reichel, Sophie Tison
PublisherSpringer Nature
Pages65-73
Number of pages9
ISBN (Print)9783540671411
Publication statusPublished - 1 Jan 2000
Event17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000 - Lille
Duration: 17 Feb 200019 Feb 2000

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1770
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000
CountryFrance
CityLille
Period17/02/0019/02/00

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A new algorithm for MAX-2-SAT'. Together they form a unique fingerprint.

  • Cite this

    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.