From backdoor key to backdoor completability: improving a known measure of hardness for the satisfiable CSP

Show simple item record

dc.contributor.author Escamocher, Guillaume
dc.contributor.author Siala, Mohamed
dc.contributor.author O'Sullivan, Barry
dc.contributor.editor van Hoeve, W. J.
dc.date.accessioned 2018-08-21T15:11:58Z
dc.date.available 2018-08-21T15:11:58Z
dc.date.issued 2018-06-08
dc.identifier.citation Escamocher G., Siala M., O’Sullivan B. (2018) From Backdoor Key to Backdoor Completability: Improving a Known Measure of Hardness for the Satisfiable CSP. In: van Hoeve WJ. (eds) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2018, Delft, Netherlands, 26-28 June, Lecture Notes in Computer Science, vol 10848. Springer, Cham, pp. 198-214. doi:10.1007/978-3-319-93031-2_14 en
dc.identifier.volume 10848 en
dc.identifier.startpage 198 en
dc.identifier.endpage 214 en
dc.identifier.isbn 978-3-319-93031-2
dc.identifier.isbn 978-3-319-93030-5
dc.identifier.issn 0302-9743
dc.identifier.uri http://hdl.handle.net/10468/6632
dc.identifier.doi 10.1007/978-3-319-93031-2_14
dc.description.abstract Many studies have been conducted on the complexity of Constraint Satisfaction Problem (CSP) classes. However, there exists little theoretical work on the hardness of individual CSP instances. In this context, the backdoor key fraction (BKF) [17] was introduced as a quantifier of problem hardness for individual satisfiable instances with regard to backtracking search. In our paper, after highlighting the weaknesses of the BKF, we propose a better characterization of the hardness of an individual satisfiable CSP instance based on the ratio between the size of the solution space and that of the search space. We formally show that our measure is negatively correlated with instance hardness. We also show through experiments that this measure evaluates more accurately the hardness of individual instances than the BKF. en
dc.description.uri https://link.springer.com/conference/cpaior en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher Springer Verlag en
dc.relation.ispartof CPAIOR 2018: International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research
dc.relation.uri https://link.springer.com/chapter/10.1007%2F978-3-319-93031-2_14
dc.rights © Springer International Publishing AG, part of Springer Nature 2018. This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Computer Science. The final authenticated version is available online at: http://dx.doi.org/10.1007/978-3-319-93031-2_14 en
dc.subject Constraint Satisfaction Problem (CSP) en
dc.subject Artificial intelligence en
dc.subject Computer programming en
dc.subject Constraint theory en
dc.subject Hardness en
dc.subject Operations research en
dc.subject Backtracking search en
dc.subject Problem hardness en
dc.subject Search spaces en
dc.subject Show through en
dc.subject Solution space en
dc.title From backdoor key to backdoor completability: improving a known measure of hardness for the satisfiable CSP en
dc.type Conference item en
dc.internal.authorcontactother Mohamed Siala, Computer Science, University College Cork, Cork, Ireland. +353-21-490-3000 Email: mohamed.siala@insight-centre.org en
dc.internal.availability Full text available en
dc.check.info Access to this article is restricted until 12 months after publication by request of the publisher. en
dc.check.date 2019-06-09
dc.date.updated 2018-08-21T14:59:09Z
dc.description.version Accepted Version en
dc.internal.rssid 450401152
dc.contributor.funder Science Foundation Ireland en
dc.description.status Peer reviewed en
dc.identifier.journaltitle Lecture Notes in Computer Science en
dc.internal.copyrightchecked No !!CORA!! en
dc.internal.licenseacceptance Yes en
dc.internal.conferencelocation Delft, Netherlands en
dc.internal.IRISemailaddress mohamed.siala@insight-centre.org en
dc.relation.project info:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/ en


Files in this item

This item appears in the following Collection(s)

Show simple item record

This website uses cookies. By using this website, you consent to the use of cookies in accordance with the UCC Privacy and Cookies Statement. For more information about cookies and how you can disable them, visit our Privacy and Cookies statement