Article ID Journal Published Year Pages File Type
428064 Information Processing Letters 2008 5 Pages PDF
Abstract

Max-SAT-CC is the following optimization problem: Given a formula in CNF and a bound k, find an assignment with at most k variables being set to true that maximizes the number of satisfied clauses among all such assignments. If each clause is restricted to have at most ℓ literals, we obtain the problem Max-ℓSAT-CC. Sviridenko [Algorithmica 30 (3) (2001) 398–405] designed a (1−e−1)-approximation algorithm for Max-SAT-CC. This result is tight unless P=NP [U. Feige, J. ACM 45 (4) (1998) 634–652]. Sviridenko asked if it is possible to achieve a better approximation ratio in the case of Max-ℓSAT-CC. We answer this question in the affirmative by presenting a randomized approximation algorithm whose approximation ratio is . To do this, we develop a general technique for adding a cardinality constraint to certain integer programs. Our algorithm can be derandomized using pairwise independent random variables with small probability space.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics