A primal–dual approximation algorithm for Minsat
| Autor: | Daya Ram Gaur, Robert Benkoczi, Ramesh Krishnamurti, Umair Arif |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
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 |
| Zdroj: | Discrete Applied Mathematics. 319:372-381 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2021.07.016 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect