Approximation Algorithm for the Max k-CSP Problem.
Moses Charikar, Konstantin Makarychev, Yury Makarychev · 2006
We present a ck 2k approximation algorithm for the Max k-CSP problem (where c> 0.44 is an absolute constant). This result improves the previously best known algorithm by Hast, which has an approximation guarantee of Ω ( k 2k log k). Our approximation guarantee matches the upper bound of Samorodnitsky and Trevisan up to a constant factor (their result assumes the Unique Games Conjecture). 1