Revisiting two-sided stability constraints

Show simple item record Siala, Mohamed O'Sullivan, Barry 2016-04-27T08:59:18Z 2016-04-27T08:59:18Z 2016-05
dc.identifier.citation Siala, M. and O’Sullivan, B. (2016) 'Revisiting Two-Sided Stability Constraints', in Quimper, C.-G. (ed.) Integration of AI and OR Techniques in Constraint Programming: 13th International Conference, CPAIOR 2016, Banff, AB, Canada, May 29 - June 1, 2016, Lecture Notes in Computer Science, vol. 9676, Cham: Springer International Publishing, pp. 342-357. doi: 10.1007/978-3-319-33954-2_25 en
dc.identifier.startpage 342 en
dc.identifier.endpage 357 en
dc.identifier.isbn 978-3-319-33954-2
dc.identifier.issn 0302-9743
dc.identifier.doi 10.1007/978-3-319-33954-2_25
dc.description.abstract We show that previous filtering propositions on two-sided stability problems do not enforce arc consistency (AC), however they maintain Bound(D) Consistency (BC(D)). We propose an optimal algorithm achieving BC(D) with O(L) time complexity where L is the length of the preference lists. We also show an adaptation of this filtering approach to achieve AC. Next, we report the first polynomial time algorithm for solving the hospital/resident problem with forced and forbidden pairs. Furthermore, we show that the particular case of this problem for stable marriage can be solved in O(n2) which improves the previously best complexity by a factor of n2. Finally, we present a comprehensive set of experiments to evaluate the filtering propositions. en
dc.description.sponsorship Science Foundation Ireland (Grant Number: SFI/12/RC/2289) en
dc.description.uri en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher Springer International Publishing en
dc.relation.ispartof International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming. Banff, Canada, 29 May-1 June, 2016.
dc.rights © Springer International Publishing AG. The final publication is available at Springer via en
dc.subject Two-sided stability en
dc.subject Arc consistency en
dc.subject Polynomial en
dc.title Revisiting two-sided stability constraints en
dc.type Conference item en
dc.internal.authorcontactother Mohamed Siala, Computer Science, University College Cork, Cork, Ireland. +353-21-490-3000 Email: en
dc.internal.availability Full text available en 2016-02-10T15:54:07Z
dc.description.version Accepted Version en
dc.internal.rssid 336045957
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!! Copyright transferred via LCNS copyright transfer form in advance of conference. Conference paper not yet presented or published. en
dc.internal.licenseacceptance Yes en
dc.internal.conferencelocation Banff, Canada en
dc.internal.IRISemailaddress 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