Theory of Computing
-------------------
Title : Approximation Algorithm for Non-Boolean Max-$k$-CSP
Authors : Konstantin Makarychev and Yury Makarychev
Volume : 10
Number : 13
Pages : 341-358
URL : https://theoryofcomputing.org/articles/v010a013
Abstract
--------
In this paper we present a randomized polynomial-time approximation
algorithm for Max-k-CSP_d. In Max-k-CSP_d we are given a set of
predicates of arity k over an alphabet of size d. Our goal is
to find an assignment that maximizes the number of satisfied
constraints.
Our algorithm has approximation factor $\Omega(kd/d^k)$ (when
$k \geq \Omega(\log d)$). The best previously known algorithm has
approximation factor $\Omega({k\log d}/{d^k})$.
Our bound is asymptotically optimal when $d = \Omega(d)$.
We also give an approximation algorithm for the Boolean Max-k-CSP_2
problem with a slightly improved approximation guarantee.