ECCC-Report TR08-008https://eccc.weizmann.ac.il/report/2008/008Comments and Revisions published for TR08-008en-usMon, 14 Apr 2008 00:00:00 +0300
Revision 1
| Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness |
Venkatesan Guruswami,
Prasad Raghavendra
https://eccc.weizmann.ac.il/report/2008/008#revision1We 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.
Mon, 14 Apr 2008 00:00:00 +0300https://eccc.weizmann.ac.il/report/2008/008#revision1
Paper TR08-008
| Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness |
Venkatesan Guruswami,
Prasad Raghavendra
https://eccc.weizmann.ac.il/report/2008/008We 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$.
Thu, 14 Feb 2008 17:11:27 +0200https://eccc.weizmann.ac.il/report/2008/008