2009 · 40 citations · 15 references
ComputingComputer ScienceAlgorithmsCombinatoricsOptimizationApproximation AlgorithmsCombinatorial OptimizationConstraint ProgrammingConstraint SatisfactionConstraint SolvingApproximation GuaranteesBoolean Constraint SatisfactionCombinatorial SearchConstraint Optimization ProblemsCsp Solving
A permutation constraint satisfaction problem (permCSP) of arity k is specified by a subset LambdasubeS <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> of permutations on {1,2,...,k}. An instance of such a permCSP consists of a set of variables V and a collection of constraints each of which is an ordered k-tuple of V. The objective is to find a global ordering sigma of the variables that maximizes the number of constraint tuples whose ordering (under sigma) follows a permutation in Lambda. This is just the natural extension of constraint satisfaction problems over finite domains (such as Boolean CSPs) to the world of ordering problems. The simplest permCSP corresponds to the case when Lambda consists of the identity permutation on two variables. This is just the maximum acyclic subgraph (MAS) problem. It was recently shown that the MAS problem is unique-games hard to approximate within a factor better than the trivial 1/2 achieved by a random ordering. Building on this work, in this paper we show that for *every* permCSP of arity 3, beating the random ordering is unique-games hard. The result is in fact stronger: we show that for every LambdasubePisube S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sub> , given an instance of permCSP(Lambda) that is almost-satisfiable, it is hard to find an ordering that satisfies more than Pi/6 +epsiv of the constraints even under the relaxed constraint Pi (for arbitrary epsiv> 0). A special case of our result is that the *Betweenness* problem is hard to approximate beyond a factor 1/3. Interestingly, for *satisfiable* instances of Betweenness, a factor 1/2 approximation algorithm is known. Thus, every permutation CSP of arity up to 3 resists approximation beyond the trivial random ordering threshold. In contrast, for Boolean CSPs, there are both approximation resistant and non-trivially approximable CSPs of arity 3.
15
On the power of unique 2-prover 1-round games
Subhash Khot · 2002 · 854 citations
Subhash Khot, Oded Regev · Journal of Computer and System Sciences · 2007 · 761 citations
Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
Subhash Khot, Guy Kindler, Elchanan Mossel et al. · SIAM Journal on Computing · 2007 · 599 citations · Full text
Optimal algorithms and inapproximability results for every CSP?
Prasad Raghavendra · 2008 · 408 citations