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

Simple item page
dc.contributor.authorEscamocher, Guillaume
dc.contributor.authorSiala, Mohamed
dc.contributor.authorO'Sullivan, Barry
dc.contributor.editorvan Hoeve, W. J.
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2018-08-21T15:11:58Z
dc.date.available2018-08-21T15:11:58Z
dc.date.issued2018-06-08
dc.date.updated2018-08-21T14:59:09Z
dc.description.abstractMany 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.statusPeer revieweden
dc.description.urihttps://link.springer.com/conference/cpaioren
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationEscamocher 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_14en
dc.identifier.doi10.1007/978-3-319-93031-2_14
dc.identifier.endpage214en
dc.identifier.isbn978-3-319-93031-2
dc.identifier.isbn978-3-319-93030-5
dc.identifier.issn0302-9743
dc.identifier.journaltitleLecture Notes in Computer Scienceen
dc.identifier.startpage198en
dc.identifier.urihttps://hdl.handle.net/10468/6632
dc.identifier.volume10848en
dc.language.isoenen
dc.publisherSpringer Verlagen
dc.relation.ispartofCPAIOR 2018: International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/en
dc.relation.urihttps://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_14en
dc.subjectConstraint Satisfaction Problem (CSP)en
dc.subjectArtificial intelligenceen
dc.subjectComputer programmingen
dc.subjectConstraint theoryen
dc.subjectHardnessen
dc.subjectOperations researchen
dc.subjectBacktracking searchen
dc.subjectProblem hardnessen
dc.subjectSearch spacesen
dc.subjectShow throughen
dc.subjectSolution spaceen
dc.titleFrom backdoor key to backdoor completability: improving a known measure of hardness for the satisfiable CSPen
dc.typeConference itemen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
5963_backdoor-key-backdoor.pdf
Size:
317.84 KB
Format:
Adobe Portable Document Format
Description:
Accepted version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Computer Science - Conference Items
Insight Centre for Data Analytics - Conference Items