Skip to main content

2015 | OriginalPaper | Buchkapitel

Profile-Based Optimal Matchings in the Student/Project Allocation Problem

verfasst von : Augustine Kwanashie, Robert W. Irving, David F. Manlove, Colin T. S. Sng

Erschienen in: Combinatorial Algorithms

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In the Student/Project Allocation problem (spa) we seek to assign students to individual or group projects offered by lecturers. Students provide a list of projects they find acceptable in order of preference. Each student can be assigned to at most one project and there are constraints on the maximum number of students that can be assigned to each project and lecturer. We seek matchings of students to projects that are optimal with respect to profile, which is a vector whose rth component indicates how many students have their rth-choice project. We present an efficient algorithm for finding agreedy maximum matching in the spa context – this is a maximum matching whose profile is lexicographically maximum. We then show how to adapt this algorithm to find a generous maximum matching – this is a matching whose reverse profile is lexicographically minimum. Our algorithms involve finding optimal flows in networks. We demonstrate how this approach can allow for additional constraints, such as lecturer lower quotas, to be handled flexibly.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Literatur
1.
Zurück zum Zitat Abraham, D.J.: Algorithmics of two-sided matching problems. Master’s thesis, University of Glasgow, Department of Computing Science (2003) Abraham, D.J.: Algorithmics of two-sided matching problems. Master’s thesis, University of Glasgow, Department of Computing Science (2003)
2.
Zurück zum Zitat 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)MathSciNetCrossRef 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)MathSciNetCrossRef
3.
Zurück zum Zitat El-Atta, A.H.A., Moussa, M.I.: Student project allocation with preference lists over (student, project) pairs. In: Proceedings of ICCEE 09: The 2nd International Conference on Computer and Electrical Engineering, pp. 375–379 (2009) El-Atta, A.H.A., Moussa, M.I.: Student project allocation with preference lists over (student, project) pairs. In: Proceedings of ICCEE 09: The 2nd International Conference on Computer and Electrical Engineering, pp. 375–379 (2009)
4.
Zurück zum Zitat Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)MATH Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)MATH
5.
Zurück zum Zitat Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge (1989)MATH Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge (1989)MATH
6.
Zurück zum Zitat Huang, C.-C., Kavitha, T., Mehlhorn, K., Michail, D.: Fair matchings and related problems. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013), vol. 24, pp. 339–350 (2013) Huang, C.-C., Kavitha, T., Mehlhorn, K., Michail, D.: Fair matchings and related problems. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013), vol. 24, pp. 339–350 (2013)
7.
Zurück zum Zitat Hylland, A., Zeckhauser, R.: The efficient allocation of individuals to positions. J. Polit. Econ. 87(2), 293–314 (1979)CrossRef Hylland, A., Zeckhauser, R.: The efficient allocation of individuals to positions. J. Polit. Econ. 87(2), 293–314 (1979)CrossRef
8.
Zurück zum Zitat Irving, R.W.: Greedy matchings. Technical Report TR-2003-136, University of Glasgow, Department of Computing Science (2003) Irving, R.W.: Greedy matchings. Technical Report TR-2003-136, University of Glasgow, Department of Computing Science (2003)
9.
Zurück zum Zitat Irving, R.W.: Greedy and generous matchings via a variant of the Bellman-Ford algorithm (2006) (Unpublished manuscript) Irving, R.W.: Greedy and generous matchings via a variant of the Bellman-Ford algorithm (2006) (Unpublished manuscript)
10.
Zurück zum Zitat Irving, R.W., Kavitha, T., Mehlhorn, K., Michail, D., Paluch, K.: Rank-maximal matchings. ACM Trans. Algorithms 2(4), 602–610 (2006)MathSciNetCrossRef Irving, R.W., Kavitha, T., Mehlhorn, K., Michail, D., Paluch, K.: Rank-maximal matchings. ACM Trans. Algorithms 2(4), 602–610 (2006)MathSciNetCrossRef
11.
Zurück zum Zitat 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)MATHMathSciNetCrossRef 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)MATHMathSciNetCrossRef
13.
Zurück zum Zitat Manlove, D.F.: Algorithmics of Matching Under Preferences. World Scientific, Singapore (2013)MATHCrossRef Manlove, D.F.: Algorithmics of Matching Under Preferences. World Scientific, Singapore (2013)MATHCrossRef
14.
Zurück zum Zitat Manlove, D.F., O’Malley, G.: Student project allocation with preferences over projects. J. Discrete Algorithms 6, 553–560 (2008)MATHMathSciNetCrossRef Manlove, D.F., O’Malley, G.: Student project allocation with preferences over projects. J. Discrete Algorithms 6, 553–560 (2008)MATHMathSciNetCrossRef
15.
Zurück zum Zitat Mehlhorn, K., Michail, D.: Network problems with non-polynomial weights and applications (2006) (Unpublished manuscript) Mehlhorn, K., Michail, D.: Network problems with non-polynomial weights and applications (2006) (Unpublished manuscript)
17.
Zurück zum Zitat Sng, C.T.S.: Efficient Algorithms for Bipartite Matching Problems with Preferences. Ph.D. thesis, University of Glasgow, Department of Computing Science (2008) Sng, C.T.S.: Efficient Algorithms for Bipartite Matching Problems with Preferences. Ph.D. thesis, University of Glasgow, Department of Computing Science (2008)
18.
Zurück zum Zitat Zelvyte, M.: The Student-Project Allocation problem: a network flow model. Honours project dissertation, University of Glasgow, School of Mathematics and Statistics (2014) Zelvyte, M.: The Student-Project Allocation problem: a network flow model. Honours project dissertation, University of Glasgow, School of Mathematics and Statistics (2014)
19.
Zurück zum Zitat Zhou, L.: On a conjecture by Gale about one-sided matching problems. J. Econ. Theor. 52(1), 123–135 (1990)MATHCrossRef Zhou, L.: On a conjecture by Gale about one-sided matching problems. J. Econ. Theor. 52(1), 123–135 (1990)MATHCrossRef
Metadaten
Titel
Profile-Based Optimal Matchings in the Student/Project Allocation Problem
verfasst von
Augustine Kwanashie
Robert W. Irving
David F. Manlove
Colin T. S. Sng
Copyright-Jahr
2015
DOI
https://doi.org/10.1007/978-3-319-19315-1_19