• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

On Exact Algorithms for Permutation CSP

Thumbnail
View/Open
publi1753.pdf (191.3Kb)
Date
2013
Dewey
Principes généraux des mathématiques
Sujet
Arity; Permutation CSP; Betweenness; Feedback Arc Set
Journal issue
Theoretical Computer Science
Volume
511
Publication date
2013
Article pages
109-116
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.tcs.2012.10.035
URI
https://basepub.dauphine.fr/handle/123456789/9755
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Kim, Eun Jung
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Gonçalves, Daniel
181 Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier [LIRMM]
Type
Article accepté pour publication ou publié
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.