A bounded approximation for the minimum cost 2-sat problem |
| |
| Authors: | Dan Gusfield and Leonard Pitt |
| |
| Affiliation: | (1) Computer Science Department, University of California at Davis, 95616 Davis, CA, USA;(2) Department of Computer Science, University of Illinois, 61801 Urbana, IL, USA |
| |
| Abstract: | 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.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. |
| |
| Keywords: | Satisfiability Combinatorial optimization Stable roommates problem Approximation algorithm |
| 本文献已被 SpringerLink 等数据库收录！ |
|
