Adding cardinality constraints to integer programs with applications to maximum satisfiability

Bläser, Markus and Heynen, Thomas and Manthey, Bodo (2008) Adding cardinality constraints to integer programs with applications to maximum satisfiability. Information Processing Letters, 105 (5). pp. 194-198. ISSN 0020-0190

PDF
Restricted to UT campus only: Request a copy
170Kb

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 1-(1-1/ℓ)ℓ-ε. 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.
Item Type:	Article
Copyright:	© 2008 Elsevier
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/79438
Official URL:	http://dx.doi.org/10.1016/j.ipl.2007.08.024
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page