On Exact Algorithms for Permutation CSP

Daniel Gonçalves 1 Eunjung Kim 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In the Permutation Constraint Satisfaction Problem (Permutation CSP) we are given a set of variables $V$ and a set of constraints C, in which constraints are tuples of elements of V. The goal is to find a total ordering of the variables, $\pi\ : V \rightarrow [1,...,|V|]$, which satisfies as many constraints as possible. A constraint $(v_1,v_2,...,v_k)$ is satisfied by an ordering $\pi$ when $\pi(v_1)<\pi(v_2)<...<\pi(v_k)$. An instance has arity $k$ if all the constraints involve at most $k$ elements. This problem expresses a variety of permutation problems including {\sc Feedback Arc Set} and {\sc Betweenness} problems. A naive algorithm, listing all the $n!$ permutations, requires $2^{O(n\log{n})}$ time. Interestingly, {\sc Permutation CSP} for arity 2 or 3 can be solved by Held-Karp type algorithms in time $O^*(2^n)$, but no algorithm is known for arity at least 4 with running time significantly better than $2^{O(n\log{n})}$. In this paper we resolve the gap by showing that {\sc Arity 4 Permutation CSP} cannot be solved in time $2^{o(n\log{n})}$ unless ETH fails.
Type de document :
Communication dans un congrès
APEX'12: International Workshop on Approximation, Parameterized and EXact Algorithms, Feb 2012, Paris, France. 2012
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00738536
Contributeur : Daniel Gonçalves <>
Soumis le : jeudi 4 octobre 2012 - 15:13:24
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

  • HAL Id : lirmm-00738536, version 1

Collections

Citation

Daniel Gonçalves, Eunjung Kim. On Exact Algorithms for Permutation CSP. APEX'12: International Workshop on Approximation, Parameterized and EXact Algorithms, Feb 2012, Paris, France. 2012. 〈lirmm-00738536〉

Partager

Métriques

Consultations de la notice

77