# 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: | |

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 |

Repository Staff Only: item control page