Skip to main content
Log in

A bounded approximation for the minimum cost 2-sat problem

  • Published:
Algorithmica Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. G. Ausiello, A. D'Atri, and M. Protasi. Structure preserving reductions among convex optimization problems.J. Comput. System Sci.,21 (1980), 136–153.

    Article  MATH  MathSciNet  Google Scholar 

  2. R. Bar-Yehuda and S. Even. A linear time approximation algorithm for the weighted vertexcover problem.J. Algorithms,2 (1981), 198–203.

    Article  MATH  MathSciNet  Google Scholar 

  3. R. Bar-Yehuda and S. Even. A local ratio theorem for approximating the weighted vertex-cover problem.Ann. Discrete Math.,25 (1985), 27–46.

    MathSciNet  Google Scholar 

  4. 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.

    Google Scholar 

  5. 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.

    Article  MathSciNet  Google Scholar 

  6. S. Even, A. Itai, and A. Shamir. On the complexity of timetable and multicommodity flow problems.SIAM J. Comput.,5(4) (1976) 691–703.

    Article  MATH  MathSciNet  Google Scholar 

  7. T. Feder, (1988). Private communication.

  8. 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.

    Google Scholar 

  9. D. Gale and L. S. Shapley. College admissions and the stability of marriage.Amer. Math. Monthly,69 (1962) 9–15.

    Article  MATH  MathSciNet  Google Scholar 

  10. M. Garey and D. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, 1979.

    MATH  Google Scholar 

  11. D. Gusfield. The structure of the stable roommate problem: efficient representation and enumeration of all stable assignments.SIAM J. Comput.,17 (1988), 742–769.

    Article  MATH  MathSciNet  Google Scholar 

  12. D. Gusfield and R. W. Irving.The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge, MA, 1989.

    MATH  Google Scholar 

  13. D. Gusfield and L. Pitt. Understanding approximations for node cover and other subset selection problems. Technical Report 308, Yale University, (1984).

  14. D. Gusfield and L. Pitt. Equivalent approximation algorithms for node cover.Inform. Process. Lett.,22(6) (1986) 291–294.

    Article  MATH  MathSciNet  Google Scholar 

  15. R. W. Irving. An efficient algorithm for the stable roommates problem.J. Algorithms,6 (1985), 577–595.

    Article  MATH  MathSciNet  Google Scholar 

  16. R. W. Irving. On the stable roommates problem. Technical Report CSC/86/R5, University of Glasgow, 1986.

  17. R. W. Irving, P. Leather, and D. Gusfield. An efficient algorithm for the “optimal” stable marriage.J. Assoc. Comput. Mach.,34 (1987), 532–543.

    MathSciNet  Google Scholar 

  18. R. M. Karp.Reducibility Among Combinatorial Problems. Plenum Press, New York, 1972, pp. 85–104.

    Google Scholar 

  19. D. E. Knuth.Mariages Stables. Les Presses de l'Université de Montréal, Montreal, 1976.

    MATH  Google Scholar 

  20. 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.

  21. 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.

    Google Scholar 

  22. A. Paz and S. Moran. NP optimization problems and their approximation.Theoret. Comput. Sci,15 (1981), 251–277.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

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

Reprints 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

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01758838

Key words

Navigation