Approximating a Generalization of MAX 2SAT and MIN 2SAT


This paper considers generalized 2SAT problems, the MAX GEN@SAT and the MIN GEN2SAT. Instances of these problems are defined on a collection of ``clauses'', which we refer to as genclauses. A genclause is any boolean function on two variables, and each genclause has a non-negative weight associated with it in the problems that are considered. The objective of MAX GEN2SAT and MIN GEN2SAT is to select a truth assignment that maximizes (minimizes) the total weight of satisfied genclauses. Goemans and Williamson used semidefinite programming and were able to provide substantial improvements in approximation factor guarantee for several important problems: MAX 2SAT, MAX CUT, MAX DICUT. In this paper we show how their approximation technique can be used to yield an approximation algorithm for \maxgensat, for which MAX 2SAT, MAX CUT, MAX DICUT are special cases. For MIN GEN2SAT, employing a recent technique of Hochbaum leads to easy recognition of which instances are polynomial or 2-approximable. Among the applications of the approximation algorithms described it is shown that the forest harvesting problem has a 0.87856-approximation algorithm.

Download Information

Click on the following title to view and download the paper in PostScript format.

Approximating a Generalization of MAX 2SAT and MIN 2SAT (22 pages, 258 KB)
Dorit S. Hochbaum and Anu Pathria. To appear in Discrete Applied Mathematics.