Rajeev Kohli

The Minimum Satisfiability Problem

Coauthor(s): Ramesh Krishnamurti, Prakash Mirchandani.

Download:

Adobe Acrobat PDF

Abstract:
This paper shows that a minimization version of satisfiability is strongly NP-hard, even if each clause contains no more than two literals and/or each clause contains at most one unnegated variable. The worst-case and average-case performances of greedy and probabilistic greedy heuristics for the problem are examined, and tight upper bounds on the performance ratio in each case are developed.

Source: SIAM Journal on Discrete Mathematics
Exact Citation:
Kohli, Rajeev, Ramesh Krishnamurti, and Prakash Mirchandani. "The Minimum Satisfiability Problem." SIAM Journal on Discrete Mathematics 7, no. 2 (1994): 275-83.
Volume: 7
Number: 2
Pages: 275-83
Date: 1994

Close Window