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.
Similar content being viewed by others
References
G. Ausiello, A. D'Atri, and M. Protasi. Structure preserving reductions among convex optimization problems.J. Comput. System Sci.,21 (1980), 136–153.
R. Bar-Yehuda and S. Even. A linear time approximation algorithm for the weighted vertexcover problem.J. Algorithms,2 (1981), 198–203.
R. Bar-Yehuda and S. Even. A local ratio theorem for approximating the weighted vertex-cover problem.Ann. Discrete Math.,25 (1985), 27–46.
S. A. Cook. The complexity of theorem proving procedures. InProceedings of the 3rd Annual ACM Symposium on Theory of Computing, New York, 1971. Association Computing Machinery, New York, pp. 151–158.
S. A. Cook and M. Luby. A simple parallel algorithm for finding a satisfying truth assignment to a 2-CNF formula.Inform. Process. Lett.,27 (1988), 141–145.
S. Even, A. Itai, and A. Shamir. On the complexity of timetable and multicommodity flow problems.SIAM J. Comput.,5(4) (1976) 691–703.
T. Feder, (1988). Private communication.
T. Feder. A new fixed point approach for stable networks and stable marriages. Unpublished manuscript, 1990. A preliminary version appears inProceedings of the 21st Annual ACM Symposium on Theory of Computing, New York, May 1989. Association of Computing Machinery, New York, pp. 513–522.
D. Gale and L. S. Shapley. College admissions and the stability of marriage.Amer. Math. Monthly,69 (1962) 9–15.
M. Garey and D. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, 1979.
D. Gusfield. The structure of the stable roommate problem: efficient representation and enumeration of all stable assignments.SIAM J. Comput.,17 (1988), 742–769.
D. Gusfield and R. W. Irving.The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge, MA, 1989.
D. Gusfield and L. Pitt. Understanding approximations for node cover and other subset selection problems. Technical Report 308, Yale University, (1984).
D. Gusfield and L. Pitt. Equivalent approximation algorithms for node cover.Inform. Process. Lett.,22(6) (1986) 291–294.
R. W. Irving. An efficient algorithm for the stable roommates problem.J. Algorithms,6 (1985), 577–595.
R. W. Irving. On the stable roommates problem. Technical Report CSC/86/R5, University of Glasgow, 1986.
R. W. Irving, P. Leather, and D. Gusfield. An efficient algorithm for the “optimal” stable marriage.J. Assoc. Comput. Mach.,34 (1987), 532–543.
R. M. Karp.Reducibility Among Combinatorial Problems. Plenum Press, New York, 1972, pp. 85–104.
D. E. Knuth.Mariages Stables. Les Presses de l'Université de Montréal, Montreal, 1976.
P. K. McKinley, N. Hasan, and C. L. Liu. Disjoint coverings in replicated nonhomogeneous arrays. Technical Report UIUCDCS-R-90-1564, University of Illinois at Urbana-Champaign, January 1990.
C. H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. InProceedings of the 20th Annual ACM Symposium on Theory of Computing, New York, May 1988. Association Computing Machinery, New York, pp. 229–234.
A. Paz and S. Moran. NP optimization problems and their approximation.Theoret. Comput. Sci,15 (1981), 251–277.
Author information
Authors and Affiliations
Additional information
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.
Rights and permissions
About this article
Cite this article
Gusfield, D., Pitt, L. A bounded approximation for the minimum cost 2-sat problem. Algorithmica 8, 103–117 (1992). https://doi.org/10.1007/BF01758838
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01758838