1. A primal–dual approximation algorithm for Minsat
- Author
-
Daya Ram Gaur, Robert Benkoczi, Ramesh Krishnamurti, and Umair Arif
- Subjects
Discrete mathematics ,Applied Mathematics ,Approximation algorithm ,0102 computer and information sciences ,02 engineering and technology ,16. Peace & justice ,Combinatorial algorithms ,01 natural sciences ,Primal dual ,Linear programming relaxation ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Computer Science::Programming Languages ,Discrete Mathematics and Combinatorics ,020201 artificial intelligence & image processing ,Boolean satisfiability problem ,Mathematics - Abstract
We characterize the optimal solution to the linear programming relaxation of the standard formulation for the minimum satisfiability problem. We give a O ( n m 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.
- Published
- 2022