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.