Improved approximation bounds for the Student-Project Allocation problem with preferences over projects
スポンサーリンク
概要
- 論文の詳細を見る
Manlove and OʼMalley (2008) 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).