zbMATH — the first resource for mathematics

An approximation algorithm for MAX-2-SAT with cardinality constraint. (English) Zbl 1266.68229
Di Battista, Giuseppe (ed.) et al., Algorithms – ESA 2003. 11th annual European symposium, Budapest, Hungary, September 16–19, 2003. Proceedings. Berlin: Springer (ISBN 3-540-20064-9/pbk). Lect. Notes Comput. Sci. 2832, 301-312 (2003).
Summary: We present a randomized polynomial-time approximation algorithm for the MAX-2-SAT problem in the presence of an extra cardinality constraint which has an asymptotic worst-case ratio of 0.75. This improves upon the previously best approximation ratio 0.6603 which was achieved by M. Bläser and B. Manthey [Lect. Notes Comput. Sci. 2518, 187–198 (2002; Zbl 1019.68136)]. Our approach is to use a solution obtained from a linear program which we first modify greedily and to which we then apply randomized rounding. The greedy phase guarantees that the errors introduced by the randomized rounding are not too large, an approach that might be interesting for other applications as well.
For the entire collection see [Zbl 1024.00048].

68W25 Approximation algorithms
68Q25 Analysis of algorithms and problem complexity
68W20 Randomized algorithms
Full Text: DOI