Academic
Publications
Student-Project Allocation with Preferences over Projects

Student-Project Allocation with Preferences over Projects,David Manlove,Gregg O'malley

Student-Project Allocation with Preferences over Projects   (Citations: 6)
BibTex | RIS | RefWorks Download
We study the problem of allocating students to projects, where both stu- dents and lecturers have preferences over projects, and both projects and lec- turers have capacities. In this context we seek a stable matching of students to projects, which respects these preference and capacity constraints. Here, the stability definition generalises the corresponding notion in the context of the classical Hospitals / Residents problem. We show that stable matchings can have dierent sizes, and the problem of finding a maximum cardinality stable matching is NP-hard, though approximable within a factor of 2.
Conference: Algorithms and Complexity in Durham - ACID , pp. 69-80, 2005
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Abstract—Student project allocations models (SPA) in which lecturers have preferences over students (projects) have been studied in [2, 3]. We present new method to construct a general student project allocation model (SPA-(s, p)) in which the lecturers have preference lists over pairs (student, project), and the students have preference lists over projects...
    • ...Manlove and O’Malley [2] presented a model for the student project allocation with preference lists over projects denoted SPA-P...
    • ...In 2005, D. F. Manlove and G. O’Malley [2] gave a student project allocation with preference over projects (SPA-P)...
    • ...The authors in [1,2] notes that a new model over (student, project) pairs may improve the results of the problem...
    • ... lଵ offers the projects pଵ pଶ and pଷ. Each project has capacity 1, whilst lଵ has capacity 2. The student sଵ prefers the project pଷ to the project pଵ and the student sଶ prefers the project pଷ to the project pଶ. This instance has two stable matching Mଵ ൌሼ ሺ sଵ ,p ଷሻ ሺ sଶ ,p ଶሻ ሽ and Mଶ ൌሼ ሺ sଵ ,p ଵሻ ሺ sଶ ,p ଷሻ ሽ . It is clearly that Mଶ is better than Mଵ but in that model it is NP problem to find best matching, the authors of SPA-p models [2] ...

    Ahmed H. Abu El-Attaet al. Student Project Allocation with Preference Lists over (Student, Projec...

    • ...(Given a graph G, the subdivision graph of G, denoted by S(G), is obtained by subdividing each edge fu; wg of G in order to obtain two edges fu; vg and fv; wg of S(G), where v is a new vertex.) It turns out that exact-mm is NP-complete for the same class of graphs [20]...

    Robert W. Irvinget al. The stable marriage problem with master preference lists

    • ...We have considered this model from an algorithmic viewpoint—see [16] for further details...

    David J. Abrahamet al. Two algorithms for the Student-Project Allocation problem

    • ...Proof. Clearly com-sm-sym is in NP. To show NP-hardness, we reduce from exact-mm in subdivision graphs, which is NP-complete [21]...

    David J. Abrahamet al. The Stable Roommates Problem with Globally-Ranked Pairs

    • ...We have considered this model from an algorithmic viewpoint ‐ see [17] for further details...

    David J. Abrahamet al. The Student-Project Allocation Problem

Sort by: