Get all the updates for this publication

Conferences

Every permutation CSP of arity 3 is approximation resistantPublished in

2009

DOI: 10.1109/CCC.2009.29

Pages: 62 - 73

A permutation constraint satisfaction problem (permCSP) of arity k is specified by a subset Λ ⊆ S k 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 σ of the variables that maximizes the number of constraint tuples whose ordering (under σ) follows a permutation in Λ. 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 Λ 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 [6]. 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 Λ ⊆ Π ⊆ S 3, given an instance of permCSP(Λ) that is almost-satisfiable, it is hard to find an ordering that satisfies more than |Π|/6 + ε of the constraints even under the relaxed constraint Π (for arbitrary ε > 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. © 2009 IEEE.

Topics: Permutation (53)%53% related to the paper, Constraint satisfaction problem (52)%52% related to the paper, Arity (52)%52% related to the paper, Hardness of approximation (51)%51% related to the paper and Approximation algorithm (50)%50% related to the paper

View more info for "Every Permutation CSP of arity 3 is Approximation Resistant"

Content may be subject to copyright.

About the journal

Journal | Proceedings of the Annual IEEE Conference on Computational Complexity |
---|---|

ISSN | 10930159 |