Cooper, Martin C. and El Mouelhi, Achref and Terrioux, Cyril and Zanuttini, Bruno On Broken Triangles. (2016) In: 25th International Joint Conference on Artificial Intelligence (IJCAI 2016), 9 July 2016 - 15 July 2016 (New York City, United States).
|
(Document in English)
PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader 184kB |
Official URL: https://www.ijcai.org/Proceedings/16/Papers/617.pdf
Abstract
A binary CSP instance satisfying the broken-triangle property (BTP) can be solved in polynomial time. Unfortunately, in practice, few instances satisfy the BTP. We show that a local version of the BTP allows the merging of domain values in binary CSPs, thus providing a novel polynomial-time reduction operation. Experimental trials on benchmark instances demonstrate a significant decrease in instance size for certain classes of problems. We show that BTP-merging can be generalised to instances with constraints of arbitrary arity. A directional version of the general-arity BTP then allows us to extend the BTP tractable class previously defined only for binary CSP.
Item Type: | Conference or Workshop Item (Paper) |
---|---|
Additional Information: | Thanks to AAAI Press editor. This papers appears in IJCAI'16 ISBN 978-1-57735-770-4 (volumes 1-3) ISBN 978-1-57735-771-1 (volumes 4-6)The definitive version is available at: https://www.ijcai.org/proceedings/2016 |
Audience (conference): | International conference proceedings |
Uncontrolled Keywords: | |
Institution: | Other partners > Aix-Marseille Université - AMU (FRANCE) French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE) Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE) Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE) Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE) Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE) Other partners > Université de Caen Basse-Normandie (FRANCE) |
Laboratory name: | |
Statistics: | download |
Deposited On: | 28 Apr 2017 13:19 |
Repository Staff Only: item control page