Given a satisfiable Boolean formula in 2-CNF, it is NP-hard to find a satisfying assignment that contains a minimum number
of true variables. A polynomial-time approximation algorithm is given that finds an assignment with at most twice as many
true variables as necessary. The algorithm also works for a weighted generalization of the problem. An application to the
optimal stable roommates problem is given in detail, and other applications are mentioned.
Key words Satisfiability - Combinatorial optimization - Stable roommates problem - Approximation algorithm
Communicated by Nimord Megiddo.
D. Gusfield was supported in part by NSF Grant CCR-8803704. Part of this work was done while he was at Yale University, partially
supported by NSF Grant MCS-8105894. L. Pitt was supported in part by NSF Grant IRI-8809570. Part of this work was done while
he was at Yale University, supported by NSF Grants MCS-8002447, MCS-8116678, and MCS-8204246.