On the Minimum Satisfiability Problem

We characterize the optimal solution to the LP relaxation of the standard formulation for the minimum satisfiability problem. Based on the characterization, we give a \(O(nm^2)\) combinatorial algorithm to solve the fractional version of the minimum satisfiability problem optimally where n(m) is the number of variables (clauses). As a by-product, we obtain a \(2(1-1/2^k)\) approximation algorithm for the minimum satisfiability problem where k is the maximum number of literals in any clause. We also give a simple linear time 2 approximation algorithm.