Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > MAX K-ALLEQUAL:
Reports tagged with Max k-AllEqual:
TR06-063 | 1st May 2006
Moses Charikar, Konstantin Makarychev, Yury Makarychev

Approximation Algorithm for the Max k-CSP Problem

We 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 ... more >>>




ISSN 1433-8092 | Imprint