Downloads: 473
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| j.jda.2012.02.001.pdf | 141.34 kB | Adobe PDF | View/Open |
| Title: | Improved approximation bounds for the Student-Project Allocation problem with preferences over projects |
| Authors: | Iwama, Kazuo  Miyazaki, Shuichi  https://orcid.org/0000-0003-0369-1970 (unconfirmed)Yanagisawa, Hiroki |
| Author's alias: | 岩間, 一雄 宮崎, 修一 柳澤, 弘揮 |
| Keywords: | The student project allocation problem Stable matching NP-hardness Approximation algorithm Approximation ratio |
| Issue Date: | May-2012 |
| Publisher: | Elsevier B.V. |
| Journal title: | Journal of Discrete Algorithms |
| Volume: | 13 |
| Start page: | 59 |
| End page: | 66 |
| Abstract: | 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). |
| Rights: | © 2012 Elsevier B.V. This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 |
| URI: | http://hdl.handle.net/2433/155464 |
| DOI(Published Version): | 10.1016/j.jda.2012.02.001 |
| Appears in Collections: | Journal Articles |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.