Approximating a Generalization of MAX 2SAT
and MIN 2SAT
Abstract
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.
dorit@hochbaum.ieor.berkeley.edu
6/6/00