JavaScript is disabled for your browser. Some features of this site may not work without it.
The submission of new items to CORA is currently unavailable due to a repository upgrade. For further information, please contact cora@ucc.ie. Thank you for your understanding.
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
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.
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