Academic Journal
Two algorithms for the Student-Project allocation problem
| العنوان: | Two algorithms for the Student-Project allocation problem |
|---|---|
| المؤلفون: | David J. Abraham, Robert W. Irving, David F. Manlove |
| المساهمون: | The Pennsylvania State University CiteSeerX Archives |
| المصدر: | http://eprints.gla.ac.uk/3439/01/irving3439.pdf. |
| سنة النشر: | 2007 |
| المجموعة: | CiteSeerX |
| الوصف: | We study the Student-Project Allocation problem (SPA), a generalisation of the classical Hospitals / Residents problem (HR). An instance of SPA involves a set of students, projects and lecturers. Each project is offered by a unique lecturer, and both projects and lecturers have capacity constraints. Students have preferences over projects, whilst lecturers have preferences over students. We present two optimal linear-time algorithms for allocating students to projects, subject to the preference and capacity constraints. In particular, each algorithm finds a stable matching of students to projects. Here, the concept of stability generalises the stability definition in the HR context. The stable matching produced by the first algorithm is simultaneously best-possible for all students, whilst the one produced by the second algorithm is simultaneously best-possible for all lecturers. We also prove some structural results concerning the set of stable matchings in a given instance of SPA. The SPA problem model that we consider is very general and has applications to a range of different contexts besides student-project allocation. |
| نوع الوثيقة: | text |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.95.9251; http://eprints.gla.ac.uk/3439/01/irving3439.pdf |
| الاتاحة: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.95.9251 http://eprints.gla.ac.uk/3439/01/irving3439.pdf |
| Rights: | Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| رقم الانضمام: | edsbas.9F2658A7 |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |