Improved approximation algorithms for Max-2SAT with cardinality constraint

Markus Bläser, Bodo Manthey

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 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 languageEnglish
Title of host publicationAlgorithms and Computation
Subtitle of host publication13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21–23, 2002 Proceedings
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages187-198
Number of pages12
ISBN (Electronic)978-3-540-36136-7
ISBN (Print)978-3-540-00142-3
DOIs
Publication statusPublished - 1 Dec 2002
Externally publishedYes
Event13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 - Vancouver, Canada
Duration: 21 Nov 200223 Nov 2002
Conference number: 13

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume2518
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th Annual International Symposium on Algorithms and Computation, ISAAC 2002
Abbreviated titleISAAC 2002
Country/TerritoryCanada
CityVancouver
Period21/11/0223/11/02

Fingerprint

Dive into the research topics of 'Improved approximation algorithms for Max-2SAT with cardinality constraint'. Together they form a unique fingerprint.

Cite this