TY - GEN
T1 - A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
AU - Buhrman, Harry
AU - Gharibian, Sevag
AU - Landau, Zeph
AU - Le Gall, François
AU - Schuch, Norbert
AU - Tamaki, Suguru
N1 - Publisher Copyright:
Copyright © 2026 by SIAM.
PY - 2026
Y1 - 2026
N2 - We present an extremely simple polynomial-space exponential-time (1 − ε)-approximation algorithm for MAX-k-SAT that is (slightly) faster than the previous known polynomial-space (1−ε)-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.
AB - We present an extremely simple polynomial-space exponential-time (1 − ε)-approximation algorithm for MAX-k-SAT that is (slightly) faster than the previous known polynomial-space (1−ε)-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.
UR - https://www.scopus.com/pages/publications/105033362416
UR - https://arxiv.org/abs/2510.18164
U2 - 10.1137/1.9781611978964.18
DO - 10.1137/1.9781611978964.18
M3 - Contribution to proceedings
AN - SCOPUS:105033362416
T3 - Symposium on Simplicity in Algorithms Proceedings
SP - 247
EP - 253
BT - Proceedings - 2026 SIAM Symposium on Simplicity in Algorithms, SOSA 2026
A2 - Assadi, Sepehr
A2 - Rotenberg, Eva
PB - Society for Industrial and Applied Mathematics Publications
T2 - 9th SIAM Symposium on Simplicity in Algorithms, SOSA 2026
Y2 - 12 January 2025 through 14 January 2025
ER -