Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT

Standard

Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. / Gramm, Jens; Hirsch, Edward A.; Niedermeier, Rolf; Rossmanith, Peter.

In: Discrete Applied Mathematics, Vol. 130, No. 2, 15.08.2003, p. 139-155.

Research output: Contribution to journal › Conference article › peer-review

Author

Gramm, Jens ; Hirsch, Edward A. ; Niedermeier, Rolf ; Rossmanith, Peter. / Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. In: Discrete Applied Mathematics. 2003 ; Vol. 130, No. 2. pp. 139-155.

BibTeX

@article{4b1c937df08047f49819e6157ee83567,

title = "Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT",

abstract = "The maximum 2-satisfiability problem (MAX-2-SAT) is: given a Boolean formula in 2-CNF, find a truth assignment that satisfies the maximum possible number of its clauses. MAX-2-SAT is MAX-SNP-complete. Recently, this problem received much attention in the contexts of (polynomial-time) approximation algorithms and (exponential-time) exact algorithms. In this paper, we present an exact algorithm solving MAX-2-SAT in time poly(L) · 2K/5, where K is the number of clauses and L is their total length. In fact, the running time is only poly(L) · 2K2/5, where K2 is the number of clauses containing two literals. This bound implies the bound poly(L) · 2L/10. Our results significantly improve previous bounds: poly(L) ·2 K/2.88 (J. Algorithms 36 (2000) 62-88) and poly(L) · 2K/3.44 (implicit in Bansal and Raman (Proceedings of the 10th Annual Conference on Algorithms and Computation, ISAAC'99, Lecture Notes in Computer Science, Vol. 1741, Springer, Berlin, 1999, pp. 247-258.)). As an application, we derive upper bounds for the (MAX-SNP-complete) maximum cut problem (MAX-CUT), showing that it can be solved in time poly(M) · 2M/3, where M is the number of edges in the graph. This is of special interest for graphs with low vertex degree.",

author = "Jens Gramm and Hirsch, {Edward A.} and Rolf Niedermeier and Peter Rossmanith",

year = "2003",

month = aug,

day = "15",

doi = "10.1016/S0166-218X(02)00402-X",

language = "English",

volume = "130",

pages = "139--155",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "2",

note = "CMMSE 2002 ; Conference date: 20-09-2002 Through 25-09-2002",

}

RIS

TY - JOUR

T1 - Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT

AU - Gramm, Jens

AU - Hirsch, Edward A.

AU - Niedermeier, Rolf

AU - Rossmanith, Peter

PY - 2003/8/15

Y1 - 2003/8/15

N2 - The maximum 2-satisfiability problem (MAX-2-SAT) is: given a Boolean formula in 2-CNF, find a truth assignment that satisfies the maximum possible number of its clauses. MAX-2-SAT is MAX-SNP-complete. Recently, this problem received much attention in the contexts of (polynomial-time) approximation algorithms and (exponential-time) exact algorithms. In this paper, we present an exact algorithm solving MAX-2-SAT in time poly(L) · 2K/5, where K is the number of clauses and L is their total length. In fact, the running time is only poly(L) · 2K2/5, where K2 is the number of clauses containing two literals. This bound implies the bound poly(L) · 2L/10. Our results significantly improve previous bounds: poly(L) ·2 K/2.88 (J. Algorithms 36 (2000) 62-88) and poly(L) · 2K/3.44 (implicit in Bansal and Raman (Proceedings of the 10th Annual Conference on Algorithms and Computation, ISAAC'99, Lecture Notes in Computer Science, Vol. 1741, Springer, Berlin, 1999, pp. 247-258.)). As an application, we derive upper bounds for the (MAX-SNP-complete) maximum cut problem (MAX-CUT), showing that it can be solved in time poly(M) · 2M/3, where M is the number of edges in the graph. This is of special interest for graphs with low vertex degree.

AB - The maximum 2-satisfiability problem (MAX-2-SAT) is: given a Boolean formula in 2-CNF, find a truth assignment that satisfies the maximum possible number of its clauses. MAX-2-SAT is MAX-SNP-complete. Recently, this problem received much attention in the contexts of (polynomial-time) approximation algorithms and (exponential-time) exact algorithms. In this paper, we present an exact algorithm solving MAX-2-SAT in time poly(L) · 2K/5, where K is the number of clauses and L is their total length. In fact, the running time is only poly(L) · 2K2/5, where K2 is the number of clauses containing two literals. This bound implies the bound poly(L) · 2L/10. Our results significantly improve previous bounds: poly(L) ·2 K/2.88 (J. Algorithms 36 (2000) 62-88) and poly(L) · 2K/3.44 (implicit in Bansal and Raman (Proceedings of the 10th Annual Conference on Algorithms and Computation, ISAAC'99, Lecture Notes in Computer Science, Vol. 1741, Springer, Berlin, 1999, pp. 247-258.)). As an application, we derive upper bounds for the (MAX-SNP-complete) maximum cut problem (MAX-CUT), showing that it can be solved in time poly(M) · 2M/3, where M is the number of edges in the graph. This is of special interest for graphs with low vertex degree.

UR - http://www.scopus.com/inward/record.url?scp=0042014171&partnerID=8YFLogxK

U2 - 10.1016/S0166-218X(02)00402-X

DO - 10.1016/S0166-218X(02)00402-X

M3 - Conference article

AN - SCOPUS:0042014171

VL - 130

SP - 139

EP - 155

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 2

T2 - CMMSE 2002

Y2 - 20 September 2002 through 25 September 2002

ER -

ID: 49828739