Interleaving solving and elicitation of constraint satisfaction problems based on expected cost

Show simple item record

dc.contributor.author Wilson, Nic
dc.contributor.author Grimes, Diarmuid
dc.contributor.author Freuder, Eugene C.
dc.date.accessioned 2013-04-24T11:52:57Z
dc.date.available 2013-04-24T11:52:57Z
dc.date.issued 2010-01
dc.identifier.citation WILSON, N., GRIMES, D. & FREUDER, E. 2010. Interleaving solving and elicitation of constraint satisfaction problems based on expected cost. Constraints, 15 (4), 540-573. doi: 10.1007/s10601-010-9099-7 en
dc.identifier.volume 15 en
dc.identifier.issued 4 en
dc.identifier.startpage 540 en
dc.identifier.endpage 573 en
dc.identifier.issn 1383-7133
dc.identifier.uri http://hdl.handle.net/10468/1083
dc.identifier.doi 10.1007/s10601-010-9099-7
dc.description.abstract We consider Constraint Satisfaction Problems in which constraints can be initially incomplete, where it is unknown whether certain tuples satisfy the constraint or not. We assume that we can determine the satisfaction of such an unknown tuple, i.e., find out whether this tuple is in the constraint or not, but doing so incurs a known cost, which may vary between tuples. We also assume that we know the probability of an unknown tuple satisfying a constraint. We define algorithms for this problem, based on backtracking search. Specifically, we consider a simple iterative algorithm based on a cost limit on the unknowns that may be determined, and a more complex algorithm that delays determining an unknown in order to estimate better whether doing so is worthwhile. We show experimentally that the more sophisticated algorithms can greatly reduce the average cost. en
dc.description.sponsorship Science Foundation Ireland (05/IN/I886); Science Foundation Ireland (08/PI/I1912) en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher Springer en
dc.relation.uri http://link.springer.com/article/10.1007%2Fs10601-010-9099-7
dc.rights © Springer Science+Business Media, LLC 2010. The final publication is available at link.springer.com. en
dc.subject Uncertain constraints en
dc.subject Incomplete CSPs en
dc.subject Interactive CSPs en
dc.subject Open constraints en
dc.subject Constraint elicitation en
dc.subject Preferences en
dc.subject Consistency en
dc.title Interleaving solving and elicitation of constraint satisfaction problems based on expected cost en
dc.type Article (peer-reviewed) en
dc.internal.authorurl http://research.ucc.ie/profiles/D005/nwilson en
dc.internal.authorcontactother Nic Wilson, Computer Science, University College Cork, Cork, Ireland. +353-21-490-3000 Email: n.wilson@4c.ucc.ie en
dc.internal.availability Full text available en
dc.date.updated 2012-12-20T17:25:07Z
dc.description.version Accepted Version en
dc.internal.rssid 70046793
dc.internal.wokid 000280893400005
dc.contributor.funder Science Foundation Ireland en
dc.description.status Peer reviewed en
dc.identifier.journaltitle Constraints en
dc.internal.copyrightchecked No. CORA - ROMEO. en
dc.internal.licenseacceptance Yes en
dc.internal.IRISemailaddress n.wilson@ucc.ie 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