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