Revisiting two-sided stability constraints

Simple item page
dc.contributor.authorSiala, Mohamed
dc.contributor.authorO'Sullivan, Barry
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2016-04-27T08:59:18Z
dc.date.available2016-04-27T08:59:18Z
dc.date.issued2016-05
dc.date.updated2016-02-10T15:54:07Z
dc.description.abstractWe 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.sponsorshipScience Foundation Ireland (Grant Number: SFI/12/RC/2289)en
dc.description.statusPeer revieweden
dc.description.urihttps://symposia.cirrelt.ca/CPAIOR2016/en/homeen
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationSiala, 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_25en
dc.identifier.doi10.1007/978-3-319-33954-2_25
dc.identifier.endpage357en
dc.identifier.isbn978-3-319-33954-2
dc.identifier.issn0302-9743
dc.identifier.journaltitleLecture Notes in Computer Scienceen
dc.identifier.startpage342en
dc.identifier.urihttps://hdl.handle.net/10468/2480
dc.language.isoenen
dc.publisherSpringer International Publishingen
dc.relation.ispartofInternational 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 https://doi.org/10.1007/978-3-319-33954-2_25en
dc.subjectTwo-sided stabilityen
dc.subjectArc consistencyen
dc.subjectPolynomialen
dc.titleRevisiting two-sided stability constraintsen
dc.typeConference itemen
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
16-cpaior.pdf
Size:
365.05 KB
Format:
Adobe Portable Document Format
Description:
Accepted Version
Download
Thumbnail Image
Name:
LNCS-Springer_Copyright_Form.pdf
Size:
54.67 KB
Format:
Adobe Portable Document Format
Description:
Copyright Transfer Agreement
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
Insight Centre for Data Analytics - Conference Items
Computer Science - Conference Items