Improved Approximation Algorithms for Max-2SAT with Cardinality Constraint

摘要

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+2·e) - ε ≈ 0.6603. Furthermore, we present a greedy algorithm with running time O(N log N) and approximation ratio 1/2. The latter algorithm even works for clauses of arbitrary length.