Article ID Journal Published Year Pages File Type
430581 Journal of Discrete Algorithms 2012 8 Pages PDF
Abstract

Manlove and OʼMalley (2008) [8] proposed the Student-Project Allocation problem with Preferences over Projects (SPA-P). They proved that the problem of finding a maximum stable matching in SPA-P is APX-hard and gave a polynomial-time 2-approximation algorithm. In this paper, we give an improved upper bound of 1.5 and a lower bound of 21/19 (>1.1052)(>1.1052).

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Improved approximation bounds for the Student-Project Allocation problem with preferences over projects
Authors
, , ,