Revisiting two-sided stability constraints

Siala, Mohamed; O'Sullivan, Barry

doi:10.1007/978-3-319-33954-2_25

UCC | UCC Library | IRIS

CORA Home

→
Research Institutes and Centres
→
Insight - Centre for Data Analytics
→
Insight - Centre for Data Analytics - Conference Items
→
View Item

Show simple item record

dc.contributor.author	Siala, Mohamed
dc.contributor.author	O'Sullivan, Barry
dc.date.accessioned	2016-04-27T08:59:18Z
dc.date.available	2016-04-27T08:59:18Z
dc.date.issued	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.uri	http://hdl.handle.net/10468/2480
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	https://symposia.cirrelt.ca/CPAIOR2016/en/home	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 https://doi.org/10.1007/978-3-319-33954-2_25	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: mohamed.siala@insight-centre.org	en
dc.internal.availability	Full text available	en
dc.date.updated	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	mohamed.siala@insight-centre.org	en