Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
| Autor: | David P. Williamson, Matthias Poloczek, Anke van Zuylen, Georg Schnitger |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
General Computer Science
Linear programming General Mathematics Order (ring theory) Approximation algorithm 0102 computer and information sciences 01 natural sciences Randomized algorithm Combinatorics 010104 statistics & probability 010201 computation theory & mathematics Maximum satisfiability problem 0101 mathematics Greedy algorithm SIMPLE algorithm Greedy randomized adaptive search procedure Mathematics |
| Zdroj: | SIAM Journal on Computing. 46:1029-1061 |
| ISSN: | 1095-7111 0097-5397 |
| DOI: | 10.1137/15m1053369 |
| Popis: | We give a simple, randomized greedy algorithm for the maximum satisfiability problem (MAX SAT) that obtains a $\frac{3}{4}$-approximation in expectation. In contrast to previously known $\frac{3}{4}$-approximation algorithms, our algorithm does not use flows or linear programming. Hence we provide a positive answer to a question posed by Williamson in 1998 on whether such an algorithm exists. Moreover, we show that Johnson's greedy algorithm cannot guarantee a $\frac{3}{4}$-approximation, even if the variables are processed in a random order. Thereby we partially solve a problem posed by Chen, Friesen, and Zheng in 1999. In order to explore the limitations of the greedy paradigm, we use the model of priority algorithms of Borodin, Nielsen, and Rackoff. Since our greedy algorithm works in an online scenario where the variables arrive with their set of undecided clauses, we wonder if a better approximation ratio can be obtained by further fine-tuning its random decisions. For a particular information model ... |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|