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 |