Date: Thursday March 25, 2004 @ 1:30pm
Place: K 8652 (Kinesiology wing)

Speaker: Ramesh Krishnamurti

Title:
The MINSAT Problem

Abstract:
Given a conjunction of clauses, each of which is a disjunction of literals, we consider the problem of deriving a truth setting that minimizes the number of clauses satisfied. The problem is strongly NP-Hard even if each clause contains no more than two literals and/or each clause contains at most one unnegated literal. We consider a simple randomized algorithm with an approximation ratio of 1/2 for this problem. We will also present the subsequent work by Marathe and Ravi, where they provide a deterministic approximation algorithm (with the same performance ratio) based on vertex cover for the problem. They also show that this is the best ratio possible (unless P=NP).

http://www.cs.sfu.ca/~cl