
On Exact Algorithms for Permutation CSP
Kim, Eun Jung; Gonçalves, Daniel (2013), On Exact Algorithms for Permutation CSP, Theoretical Computer Science, 511, p. 109-116. 10.1016/j.tcs.2012.10.035
View/ Open
Type
Article accepté pour publication ou publiéDate
2013Journal name
Theoretical Computer ScienceVolume
511Publisher
Elsevier
Pages
109-116
Publication identifier
Metadata
Show full item recordAuthor(s)
Kim, Eun JungLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Gonçalves, Daniel
Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier [LIRMM]
Abstract (EN)
In the Permutation Constraint Satisfaction Problem (Permutation CSP) we are given a set of variables V and a set of constraints C, in which constraint s are tuples of elem ent s of V . The goal is to find a total ordering of the variables, π : V → [1, . . . , |V |], which satisfies as m any constraints as possible. A constraint ( v1, v2, . . . , vk) is satisfied by an ordering π when π ( v1) < π ( v2) < . . . < π ( vk) . An instance has arity k if all the constraint s involve at most k elements. This problem expresses a variety of permut at ion problem s including Feedback Arc Set an d Betweenness problems. A naïve algorithm , listing all then! permutation s, requires 2O(n log n) time. Interestingly, Permutation CSP for arity 2 or 3 can be solved by Held - Karptype algorithms in time O ∗ ( 2n) , but no algorithm is known for arity at least 4 with running time significantly better than 2O(n log n). In this paper we resolve the gap by showing that Arity 4 Permutation CSP can not be solved in time 2o(n log n) unless ETH fails.Subjects / Keywords
Arity; Permutation CSP; Betweenness; Feedback Arc SetRelated items
Showing items related by title and author.
-
Cohen, Nathann; Gonçalves, Daniel; Kim, Eun Jung; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2017) Article accepté pour publication ou publié
-
Kim, Eun Jung; Kratsch, Stefan; Pilipczuk, Marcin; Wahlström, Magnus (2023) Communication / Conférence
-
Dell, Holger; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Mömke, Tobias (2017) Article accepté pour publication ou publié
-
Dell, Holger; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Mömke, Tobias (2015) Communication / Conférence
-
Kanté, Mamadou Moustapha; Kim, Eun Jung; Kwon, O-joung; Paul, Christophe (2017) Article accepté pour publication ou publié