Top

Published in:

2020 | OriginalPaper | Chapter

An Algorithm for Strong Stability in the Student-Project Allocation Problem with Ties

Authors : Sofiat Olaosebikan, David Manlove

Published in: Algorithms and Discrete Applied Mathematics

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We study a variant of the Student-Project Allocation problem with lecturer preferences over Students where ties are allowed in the preference lists of students and lecturers (spa-st). We investigate the concept of strong stability in this context. Informally, a matching is strongly stable if there is no student and lecturer l such that if they decide to form a private arrangement outside of the matching via one of l’s proposed projects, then neither party would be worse off and at least one of them would strictly improve. We describe the first polynomial-time algorithm to find a strongly stable matching or report that no such matching exists, given an instance of spa-st. Our algorithm runs in \(O(m^2)\) time, where m is the total length of the students’ preference lists.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter A New Model in Firefighting Theory

next chapter Overlaying a Hypergraph with a Graph with Bounded Maximum Degree

An edge \((s_i, p_j) \in E\) can change state from bound to unbound, but not vice versa.

If \(s_i\) is bound to more than one projects offered by \(l_k\), for all the bound edges involving \(s_i\) and these projects that we remove from \(G_r\), we only reduce \(l_k\)’s quota in \(G_r\) by one.

An intuition as to why we add dummy students to \(G_r\) is as follows. Given a lecturer \(l_k\) whose project is provisionally assigned to a student in \(G_r\). If \(q_k^* < \sum \{q_j^* : p_j \in P_k \cap P_r\}\), then we need n dummy students to offset the difference between \(\sum \{q_j^* : p_j \in P_k \cap P_r\}\) and \(q_k^*\), so that we do not oversubscribe \(l_k\) in any maximum matching obtained from \(G_r\).

This type of deletion was also carried out in Algorithm SPA-ST-super for super-stability [23].

By making sure that all the dummy students are matched in step 1, we are guaranteed that no lecturer is oversubscribed with non-dummy students in \(G_r\).

Abraham, D.J., Irving, R.W., Manlove, D.F.: Two algorithms for the Student-Project allocation problem. J. Discrete Algorithms 5(1), 79–91 (2007)MathSciNetMATHCrossRef

Abu El-Atta, A.H., Moussa, M.I.: Student project allocation with preference lists over (student, project) pairs. In: Proceedings of ICCEE 2009, pp. 375–379 (2009)

Baidas, M., Bahbahani, Z., Alsusa, E.: User association and channel assignment in downlink multi-cell NOMA networks: a matching-theoretic approach. EURASIP J. Wirel. Commun. Netw. 2019, 220 (2019)CrossRef

Baidas, M., Bahbahani, M., Alsusa, E., Hamdi, K., Ding, Z.: D2D group association and channel assignment in uplink multi-cell NOMA networks: a matching theoretic approach. IEEE Trans. Commun. 67, 8771–8785 (2019)CrossRef

Baidas, M., Bahbahani, Z., El-Sharkawi, N., Shehada, H., Alsusa, E.: Joint relay selection and max-min energy-efficient power allocation in downlink multicell NOMA networks: a matching-theoretic approach. Trans. Emerg. Telecommun. Technol. 30, 5 (2019)

Chiarandini, M., Fagerberg, R., Gualandi, S.: Handling preferences in student-project allocation. Ann. Oper. Res. 275(1), 39–78 (2019)MathSciNetMATHCrossRef

Cooper, F., Manlove, D.: A 3/2-Approximation algorithm for the student-project allocation problem. In: Proceedings of SEA 2018. Leibniz International Proceedings in Informatics (LIPIcs), vol. 103, pp. 8:1–8:13 (2018)

Irving, R.W.: Stable marriage and indifference. Discrete Appl. Math. 48, 261–272 (1994)MathSciNetMATHCrossRef

Irving, R.W., Manlove, D.F., Scott, S.: The hospitals/residents problem with ties. SWAT 2000. LNCS, vol. 1851, pp. 259–271. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44985-X_24CrossRef

10.

Irving, R.W., Manlove, D.F., Scott, S.: Strong stability in the hospitals/residents problem. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 439–450. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36494-3_39CrossRef

11.

Iwama, K., Miyazaki, S., Morita, Y., Manlove, D.: Stable marriage with incomplete lists and ties. In: Wiedermann, J., van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 443–452. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48523-6_41MATHCrossRef

12.

Iwama, K., Miyazaki, S., Yanagisawa, H.: Improved approximation bounds for the student-project allocation problem with preferences over projects. J. Discrete Algorithms 13, 59–66 (2012)MathSciNetMATHCrossRef

13.

Kavitha, T., Mehlhorn, K., Michail, D., Paluch, K.: Strongly stable matchings in time O(nm) and extension to the hospitals-residents problem. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 222–233. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24749-4_20CrossRef

14.

Kazakov, D.: Co-ordination of student-project allocation. Manuscript, University of York, Department of Computer Science (2001). http://www-users.cs.york.ac.uk/kazakov/papers/proj.pdf. Accessed 25 Nov 2019

15.

Kwanashie, A., Irving, R.W., Manlove, D.F., Sng, C.T.S.: Profile-based optimal matchings in the Student/project Allocation problem. In: Kratochvíl, J., Miller, M., Froncek, D. (eds.) IWOCA 2014. LNCS, vol. 8986, pp. 213–225. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-19315-1_19CrossRef

16.

Kunysz, A.: An algorithm for the maximum weight strongly stable matching problem. In: Proceedings of ISAAC 2018. LIPIcs, vol. 123, pp. 42:1–42:13 (2018)

17.

Liu, C.L.: Introduction to Combinatorial Mathematics. McGraw-Hill, New York (1968)MATH

18.

Manlove, D.: Stable marriage with ties and unacceptable partners. Technical report TR-1999-29, University of Glasgow, Department of Computing Science, January 1999

19.

Manlove, D.: Algorithmics of Matching Under Preferences. World Scientific, Singapore (2013)MATHCrossRef

20.

Manlove, D., Irving, R.W., Iwama, K., Miyazaki, S., Morita, Y.: Hard variants of stable marriage. Theor. Comput. Sci. 276(1–2), 261–279 (2002)MathSciNetMATHCrossRef

21.

Manlove, D., Milne, D., Olaosebikan, S.: An integer programming approach to the student-project allocation problem with preferences over projects. In: Lee, J., Rinaldi, G., Mahjoub, A.R. (eds.) ISCO 2018. LNCS, vol. 10856, pp. 313–325. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96151-4_27CrossRef

22.

Manlove, D., O’Malley, G.: Student project allocation with preferences over projects. J. Discrete Algorithms 6, 553–560 (2008)MathSciNetMATHCrossRef

23.

Olaosebikan, S., Manlove, D.: Super-stability in the student-project allocation problem with ties. In: Kim, D., Uma, R.N., Zelikovsky, A. (eds.) COCOA 2018. LNCS, vol. 11346, pp. 357–371. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-04651-4_24CrossRef

24.

Olaosebikan, S., Manlove, D.F.: An Algorithm for Strong Stability in the Student-Project Allocation problem with Ties. CoRR, abs/1911.10262 (2019). http://arxiv.org/abs/1911.10262

25.

Roth, A.E.: The evolution of the labor market for medical interns and residents: a case study in game theory. J. Polit. Econ. 92(6), 991–1016 (1984)CrossRef

Title: An Algorithm for Strong Stability in the Student-Project Allocation Problem with Ties
Authors: Sofiat Olaosebikan
David Manlove
Publisher: Springer International Publishing
Book: Algorithms and Discrete Applied Mathematics
Print ISBN: 978-3-030-39218-5

Electronic ISBN: 978-3-030-39219-2

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-39219-2_31

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner