Show simple item record

On Exact Algorithms for Permutation CSP

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorKim, Eun Jung*
hal.structure.identifierLaboratoire d'Informatique de Robotique et de Microélectronique de Montpellier [LIRMM]
dc.contributor.authorGonçalves, Daniel
HAL ID: 7100		*
dc.date.accessioned2012-07-16T12:39:46Z
dc.date.available2012-07-16T12:39:46Z
dc.date.issued2013
dc.identifier.issn0304-3975
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/9755
dc.language.isoenen
dc.subjectArity
dc.subjectPermutation CSP
dc.subjectBetweenness
dc.subjectFeedback Arc Set
dc.subject.ddc511en
dc.titleOn Exact Algorithms for Permutation CSP
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherLIRMM, Univ. Montpellier 2 and CNRS;France
dc.description.abstractenIn 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.
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol511
dc.relation.isversionofjnldate2013
dc.relation.isversionofjnlpages109-116
dc.relation.isversionofdoi10.1016/j.tcs.2012.10.035
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2016-05-28T14:09:00Z
hal.faultCode{"duplicate-entry":{"lirmm-01263918":{"doi":"1.0"}}}
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
publi1753.pdf
Size:
191.3Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record