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 |