2012年5月
Improved approximation bounds for the Student-Project Allocation problem with preferences over projects
Journal of Discrete Algorithms
- ,
- ,
- 巻
- 13
- 号
- 開始ページ
- 59
- 終了ページ
- 66
- 記述言語
- 英語
- 掲載種別
- 研究論文（学術雑誌）
- DOI
- 10.1016/j.jda.2012.02.001
Manlove and OMalley (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). © 2012 Elsevier B.V. All rights reserved.
1.1052). © 2012 Elsevier B.V. All rights reserved.
- リンク情報
- ID情報
-
- DOI : 10.1016/j.jda.2012.02.001
- ISSN : 1570-8667
- DBLP ID : journals/jda/IwamaMY12
- CiNii Articles ID : 120004057186
- SCOPUS ID : 84859793233