Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR08-008 | 14th April 2008 00:00

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

RSS-Feed




Revision #1
Authors: Venkatesan Guruswami, Prasad Raghavendra
Accepted on: 14th April 2008 00:00
Downloads: 1320
Keywords: 


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.


Paper:

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



ISSN 1433-8092 | Imprint