A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910151121829888 |
|---|---|
| author | Buhrman, Harry Gharibian, Sevag Landau, Zeph Gall, François Le Schuch, Norbert Tamaki, Suguru |
| author_facet | Buhrman, Harry Gharibian, Sevag Landau, Zeph Gall, François Le Schuch, Norbert Tamaki, Suguru |
| contents | We present an extremely simple polynomial-space exponential-time $(1-\varepsilon)$-approximation algorithm for MAX-k-SAT that is (slightly) faster than the previous known polynomial-space $(1-\varepsilon)$-approximation algorithms by Hirsch (Discrete Applied Mathematics, 2003) and Escoffier, Paschos and Tourniaire (Theoretical Computer Science, 2014). Our algorithm repeatedly samples an assignment uniformly at random until finding an assignment that satisfies a large enough fraction of clauses. Surprisingly, we can show the efficiency of this simpler approach by proving that in any instance of MAX-k-SAT (or more generally any instance of MAXCSP), an exponential number of assignments satisfy a fraction of clauses close to the optimal value. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_18164 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT Buhrman, Harry Gharibian, Sevag Landau, Zeph Gall, François Le Schuch, Norbert Tamaki, Suguru Data Structures and Algorithms Computational Complexity We present an extremely simple polynomial-space exponential-time $(1-\varepsilon)$-approximation algorithm for MAX-k-SAT that is (slightly) faster than the previous known polynomial-space $(1-\varepsilon)$-approximation algorithms by Hirsch (Discrete Applied Mathematics, 2003) and Escoffier, Paschos and Tourniaire (Theoretical Computer Science, 2014). Our algorithm repeatedly samples an assignment uniformly at random until finding an assignment that satisfies a large enough fraction of clauses. Surprisingly, we can show the efficiency of this simpler approach by proving that in any instance of MAX-k-SAT (or more generally any instance of MAXCSP), an exponential number of assignments satisfy a fraction of clauses close to the optimal value. |
| title | A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2510.18164 |