Improved approximation bounds for the Student-Project Allocation problem with preferences over projects ?
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 ) .
stable matching the student project allocation problem np-hardness approximation algorithm approximation ratio