A bounded approximation for the minimum cost 2-sat problem

Dan Gusfield, Leonard Pitt

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)103-117
Number of pages15
JournalAlgorithmica
Volume8
Issue number1-6
DOIs
StatePublished - Dec 1 1992

Keywords

  • Approximation algorithm
  • Combinatorial optimization
  • Satisfiability
  • Stable roommates problem

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A bounded approximation for the minimum cost 2-sat problem'. Together they form a unique fingerprint.

Cite this