Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism Read chapter Read first chapter

2015 | OriginalPaper | Chapter

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

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

Published in: Combinatorial Algorithms

Publisher: Springer International Publishing

Log in

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

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.

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 On Maximum Common Subgraph Problems in Series-Parallel Graphs
next chapter The Min-max Edge q-Coloring Problem
Literature
1.
Abraham, D.J.: Algorithmics of two-sided matching problems. Master’s thesis, University of Glasgow, Department of Computing Science (2003)
2.
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.
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.
Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)MATH
5.
Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge (1989)MATH
6.
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.
Hylland, A., Zeckhauser, R.: The efficient allocation of individuals to positions. J. Polit. Econ. 87(2), 293–314 (1979)CrossRef
8.
Irving, R.W.: Greedy matchings. Technical Report TR-2003-136, University of Glasgow, Department of Computing Science (2003)
9.
Irving, R.W.: Greedy and generous matchings via a variant of the Bellman-Ford algorithm (2006) (Unpublished manuscript)
10.
Irving, R.W., Kavitha, T., Mehlhorn, K., Michail, D., Paluch, K.: Rank-maximal matchings. ACM Trans. Algorithms 2(4), 602–610 (2006)MathSciNetCrossRef
11.
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
12.
13.
Manlove, D.F.: Algorithmics of Matching Under Preferences. World Scientific, Singapore (2013)MATHCrossRef
14.
Manlove, D.F., O’Malley, G.: Student project allocation with preferences over projects. J. Discrete Algorithms 6, 553–560 (2008)MATHMathSciNetCrossRef
15.
Mehlhorn, K., Michail, D.: Network problems with non-polynomial weights and applications (2006) (Unpublished manuscript)
16.
17.
Sng, C.T.S.: Efficient Algorithms for Bipartite Matching Problems with Preferences. Ph.D. thesis, University of Glasgow, Department of Computing Science (2008)
18.
Zelvyte, M.: The Student-Project Allocation problem: a network flow model. Honours project dissertation, University of Glasgow, School of Mathematics and Statistics (2014)
19.
Zhou, L.: On a conjecture by Gale about one-sided matching problems. J. Econ. Theor. 52(1), 123–135 (1990)MATHCrossRef
Metadata
Title
Profile-Based Optimal Matchings in the Student/Project Allocation Problem
Authors
Augustine Kwanashie
Robert W. Irving
David F. Manlove
Colin T. S. Sng
Copyright Year
2015
Book
Combinatorial Algorithms

Print ISBN: 978-3-319-19314-4

Electronic ISBN: 978-3-319-19315-1

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-19315-1_19

Premium Partner

    Image Credits