An integer programming approach to the student-project allocation problem with preferences over projects
From MaRDI portal
Publication:1661903
DOI10.1007/978-3-319-96151-4_27zbMATH Open1403.90580arXiv1804.09993OpenAlexW2798889959MaRDI QIDQ1661903FDOQ1661903
Authors: Duncan Milne, Sofiat Olaosebikan, David F. Manlove 
Publication date: 17 August 2018
Abstract: The Student-Project Allocation problem with preferences over Projects (SPA-P) involves sets of students, projects and lecturers, where the students and lecturers each have preferences over the projects. In this context, we typically seek a stable matching of students to projects (and lecturers). However, these stable matchings can have different sizes, and the problem of finding a maximum stable matching (MAX-SPA-P) is NP-hard. There are two known approximation algorithms for MAX-SPA-P, with performance guarantees of 2 and 3/2. In this paper, we describe an Integer Programming (IP) model to enable MAX-SPA-P to be solved optimally. Following this, we present results arising from an empirical analysis that investigates how the solution produced by the approximation algorithms compares to the optimal solution obtained from the IP model, with respect to the size of the stable matchings constructed, on instances that are both randomly-generated and derived from real datasets. Our main finding is that the 3/2-approximation algorithm finds stable matchings that are very close to having maximum cardinality.
Full work available at URL: https://arxiv.org/abs/1804.09993
Recommendations
- Student-project allocation with preferences over projects: algorithmic and experimental results
- A 3 / 2 -approximation Algorithm for the Student-Project Allocation Problem
- Student-project allocation with preferences over projects
- Improved approximation bounds for the student-project allocation problem with preferences over projects
- Improved approximation bounds for the student-project allocation problem with preferences over projects
Cited In (7)
- Efficiency and fairness criteria in the assignment of students to projects
- Microthesis: The student-project allocation problem
- Super-stability in the student-project allocation problem with ties
- A 3 / 2 -approximation Algorithm for the Student-Project Allocation Problem
- Algorithms and Computation
- Student-project allocation with preferences over projects: algorithmic and experimental results
- An optimization model for the student-to-project supervisor assignment problem-the case of an engineering department
Uses Software
This page was built for publication: An integer programming approach to the student-project allocation problem with preferences over projects
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1661903)
