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)$.