Please use this identifier to cite or link to this item:
https://hdl.handle.net/20.500.14365/3963
Title: | The Parameterized Complexity of Global Constraints | Authors: | Bessiere C. Hebrard E. Hnich B. Kiziltan Z. Quimper C.-G. Walsh T. |
Keywords: | Artificial intelligence Computer programming Constraint theory Packet networks Approximability Bounded sizes Constraint programmings Constraint propagations Dynamic programs Global constraints Parameterized complexities Bionics |
Abstract: | We argue that parameterized complexity is a useful tool with which to study global constraints. In particular, we show that many global constraints which are intractable to propagate completely have natural parameters which make them fixed-parameter tractable and which are easy to compute. This tractability tends either to be the result of a simple dynamic program or of a decomposition which has a strong backdoor of bounded size. This strong backdoor is often a cycle cutset. We also show that parameterized complexity can be used to study other aspects of constraint programming like symmetry breaking. For instance, we prove that value symmetry is fixed-parameter tractable to break in the number of symmetries. Finally, we argue that parameterized complexity can be used to derive results about the approximability of constraint propagation. Copyright © 2008, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. | Description: | Cornell Univ. Intelligent Information Systems Inst.;Toyota Motor Engineering and Manufacturing North America Inc.;ACM/SIGART;Boeing 23rd AAAI Conference on Artificial Intelligence and the 20th Innovative Applications of Artificial Intelligence Conference, AAAI-08/IAAI-08 -- 13 July 2008 through 17 July 2008 -- Chicago, IL -- 74777 |
URI: | https://hdl.handle.net/20.500.14365/3963 | ISBN: | 9.78E+12 |
Appears in Collections: | Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection |
Show full item record
CORE Recommender
SCOPUSTM
Citations
22
checked on Mar 26, 2025
Page view(s)
74
checked on Mar 31, 2025
Download(s)
6
checked on Mar 31, 2025
Google ScholarTM
Check
Altmetric
Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.