__
Revision #1 to TR08-008 | 14th April 2008 00:00
__
#### Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness

**Abstract:**
We study the approximability of the \maxcsp problem over non-boolean

domains, more specifically over $\{0,1,\ldots,q-1\}$ for some

integer $q$. We extend the techniques of Samorodnitsky and

Trevisan to obtain a UGC hardness result when $q$ is

a prime. More precisely, assuming the Unique Games Conjecture, we

show that it is NP-hard to approximate the problem to a ratio

greater than $q^2k/q^k$. Independent of this work, Austrin and

Mossel obtain a more general UGC hardness result

using entirely different techniques.

We also obtain an approximation algorithm that achieves a ratio of

$C(q) \cdot k/q^k$ for some constant $C(q)$ depending only on $q$.

Except for constant factors depending on $q$, the algorithm and the

UGC hardness result have the same dependence on the arity $k$. It

has been pointed out to us by Makarychev and Makarychev that a similar

approximation ratio can be obtained by reducing the non-boolean case

to a boolean CSP, and appealing to the CMM algorithm.

As a subroutine, we design a constant factor (depending on $q$)

approximation algorithm for the problem of maximizing a semidefinite

quadratic form, where the variables are constrained to take values

on the corners of the $q$-dimensional simplex. This result

generalizes an algorithm of Nesterov for maximizing

semidefinite quadratic forms where the variables take $\{-1,1\}$

values.

__
TR08-008 | 8th February 2008 00:00
__

#### Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness

**Abstract:**
We study the approximability of the \maxcsp problem over non-boolean domains, more specifically over $\{0,1,\ldots,q-1\}$ for some integer $q$. We obtain a approximation algorithm that achieves a ratio of $C(q) \cdot k/q^k$ for some constant $C(q)$ depending only on $q$. Further, we extend the techniques of Samorodnitsky and Trevisan to obtain a UGC hardness result when $q$ is a prime. More precisely, assuming the Unique Games Conjecture, we show that it is NP-hard to approximate the problem to a ratio greater than $q^2k/q^k$. Except for constant factors depending on $q$, the algorithm and the UGC hardness result have the same dependence on the arity $k$.