Improved approximation algorithms for Max-2SAT with cardinality constraint

Markus Bläser; Bodo Manthey

doi:10.1007/3-540-36136-7_17

Improved approximation algorithms for Max-2SAT with cardinality constraint

Markus Bläser, Bodo Manthey

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

7 Citations (Scopus)

Abstract

The optimization problem Max-2SAT-CC is Max-2SAT with the additional cardinality constraint that the value one may be assigned to at most K variables. We present an approximation algorithm with polynomial running time for Max-2SAT-CC. This algorithm achieves, for any ε > 0, approximation ratio 6+3.e/16+3.e - ε ≈ 0.6603. Furthermore, we present a greedy algorithm with running time O(Nlog N) and approximation ratio I. The latter algorithm even works for clauses of arbitrary length.

Original language	English
Title of host publication	Algorithms and Computation
Subtitle of host publication	13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21–23, 2002 Proceedings
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	187-198
Number of pages	12
ISBN (Electronic)	978-3-540-36136-7
ISBN (Print)	978-3-540-00142-3
DOIs	https://doi.org/10.1007/3-540-36136-7_17
Publication status	Published - 1 Dec 2002
Externally published	Yes
Event	13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 - Vancouver, Canada Duration: 21 Nov 2002 → 23 Nov 2002 Conference number: 13

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2518
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	13th Annual International Symposium on Algorithms and Computation, ISAAC 2002
Abbreviated title	ISAAC 2002
Country/Territory	Canada
City	Vancouver
Period	21/11/02 → 23/11/02

Access to Document

10.1007/3-540-36136-7_17

Cite this

@inproceedings{e6c50d245b3943a78ea7717c9488d696,

title = "Improved approximation algorithms for Max-2SAT with cardinality constraint",

abstract = "The optimization problem Max-2SAT-CC is Max-2SAT with the additional cardinality constraint that the value one may be assigned to at most K variables. We present an approximation algorithm with polynomial running time for Max-2SAT-CC. This algorithm achieves, for any ε > 0, approximation ratio 6+3.e/16+3.e - ε ≈ 0.6603. Furthermore, we present a greedy algorithm with running time O(Nlog N) and approximation ratio I. The latter algorithm even works for clauses of arbitrary length.",

author = "Markus Bl{\"a}ser and Bodo Manthey",

year = "2002",

month = dec,

day = "1",

doi = "10.1007/3-540-36136-7_17",

language = "English",

isbn = "978-3-540-00142-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "187--198",

booktitle = "Algorithms and Computation",

note = "13th Annual International Symposium on Algorithms and Computation, ISAAC 2002, ISAAC 2002 ; Conference date: 21-11-2002 Through 23-11-2002",

}

Bläser, M & Manthey, B 2002, Improved approximation algorithms for Max-2SAT with cardinality constraint. in Algorithms and Computation: 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21–23, 2002 Proceedings. Lecture Notes in Computer Science, vol. 2518, Springer, Berlin, Heidelberg, pp. 187-198, 13th Annual International Symposium on Algorithms and Computation, ISAAC 2002, Vancouver, British Columbia, Canada, 21/11/02. https://doi.org/10.1007/3-540-36136-7_17

Improved approximation algorithms for Max-2SAT with cardinality constraint. / Bläser, Markus; Manthey, Bodo.
Algorithms and Computation: 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21–23, 2002 Proceedings. Berlin, Heidelberg: Springer, 2002. p. 187-198 (Lecture Notes in Computer Science; Vol. 2518).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Improved approximation algorithms for Max-2SAT with cardinality constraint

AU - Bläser, Markus

AU - Manthey, Bodo

N1 - Conference code: 13

PY - 2002/12/1

Y1 - 2002/12/1

N2 - The optimization problem Max-2SAT-CC is Max-2SAT with the additional cardinality constraint that the value one may be assigned to at most K variables. We present an approximation algorithm with polynomial running time for Max-2SAT-CC. This algorithm achieves, for any ε > 0, approximation ratio 6+3.e/16+3.e - ε ≈ 0.6603. Furthermore, we present a greedy algorithm with running time O(Nlog N) and approximation ratio I. The latter algorithm even works for clauses of arbitrary length.

AB - The optimization problem Max-2SAT-CC is Max-2SAT with the additional cardinality constraint that the value one may be assigned to at most K variables. We present an approximation algorithm with polynomial running time for Max-2SAT-CC. This algorithm achieves, for any ε > 0, approximation ratio 6+3.e/16+3.e - ε ≈ 0.6603. Furthermore, we present a greedy algorithm with running time O(Nlog N) and approximation ratio I. The latter algorithm even works for clauses of arbitrary length.

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

U2 - 10.1007/3-540-36136-7_17

DO - 10.1007/3-540-36136-7_17

M3 - Conference contribution

AN - SCOPUS:84878640869

SN - 978-3-540-00142-3

T3 - Lecture Notes in Computer Science

SP - 187

EP - 198

BT - Algorithms and Computation

PB - Springer

CY - Berlin, Heidelberg

T2 - 13th Annual International Symposium on Algorithms and Computation, ISAAC 2002

Y2 - 21 November 2002 through 23 November 2002

ER -

Improved approximation algorithms for Max-2SAT with cardinality constraint

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this