Profile-based optimal matchings in the student-project allocation problem

Kwanashie, A. and Irving, R. W. and Manlove, D. (2016) Profile-based optimal matchings in the student-project allocation problem. [Data Collection]

Enlighten Publications URI: http://eprints.gla.ac.uk/id/eprint/105144

Collection description

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.

College / School: College of Science and Engineering > School of Computing Science
Date Deposited: 20 Jan 2016 10:08
Enlighten Publications URL: http://eprints.gla.ac.uk/105144/
Retention date: 20 January 2026
Funder's Name: Engineering & Physical Sciences Research Council (EPSRC)
URI: http://researchdata.gla.ac.uk/id/eprint/253

Available Files

Data

Read me

Repository Staff Only: Update this record

Kwanashie, A. and Irving, R. W. and Manlove, D. (2016); Profile-based optimal matchings in the student-project allocation problem

University of Glasgow

10.5525/gla.researchdata.253

Retrieved: 2017-11-18

Downloads

Downloads per month over past year