ECCC-Report TR06-063https://eccc.weizmann.ac.il/report/2006/063Comments and Revisions published for TR06-063en-usMon, 08 May 2006 18:36:22 +0300
Paper TR06-063
| Approximation Algorithm for the Max k-CSP Problem |
Moses Charikar,
Konstantin Makarychev,
Yury Makarychev
https://eccc.weizmann.ac.il/report/2006/063We present a c.k/2^k 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 Omega(k/(2^k 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).
Mon, 08 May 2006 18:36:22 +0300https://eccc.weizmann.ac.il/report/2006/063