ダウンロード数: 429
このアイテムのファイル:
| ファイル | 記述 | サイズ | フォーマット | |
|---|---|---|---|---|
| j.jda.2012.02.001.pdf | 141.34 kB | Adobe PDF | 見る/開く |
| タイトル: | Improved approximation bounds for the Student-Project Allocation problem with preferences over projects |
| 著者: | Iwama, Kazuo  Miyazaki, Shuichi  https://orcid.org/0000-0003-0369-1970 (unconfirmed)Yanagisawa, Hiroki |
| 著者名の別形: | 岩間, 一雄 宮崎, 修一 柳澤, 弘揮 |
| キーワード: | The student project allocation problem Stable matching NP-hardness Approximation algorithm Approximation ratio |
| 発行日: | May-2012 |
| 出版者: | Elsevier B.V. |
| 誌名: | Journal of Discrete Algorithms |
| 巻: | 13 |
| 開始ページ: | 59 |
| 終了ページ: | 66 |
| 抄録: | 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). |
| 著作権等: | © 2012 Elsevier B.V. This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 |
| URI: | http://hdl.handle.net/2433/155464 |
| DOI(出版社版): | 10.1016/j.jda.2012.02.001 |
| 出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。