Improved Approximation Algorithms for Max-2SAT with Cardinality Constraint

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