ダウンロード数: 191
このアイテムのファイル:
| ファイル | 記述 | サイズ | フォーマット | |
|---|---|---|---|---|
| 978-3-642-20877-5_43.pdf | 171.58 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 |
| 著者名の別形: | 岩間, 一雄 宮崎, 修一 柳澤, 弘揮 |
| 発行日: | 2011 |
| 出版者: | Springer Berlin Heidelberg |
| 誌名: | Lecture Notes in Computer Science |
| 巻: | 6648 |
| 開始ページ: | 440 |
| 終了ページ: | 451 |
| 抄録: | Manlove and O’Malley [9] 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)21/19 (>1.1052) . |
| 記述: | 'Theory and Applications of Models of Computation' 8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011. Proceedings |
| 著作権等: | The final publication is available at Springer via https://doi.org/10.1007/978-3-319-18173-8_27 This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 |
| URI: | http://hdl.handle.net/2433/226946 |
| DOI(出版社版): | 10.1007/978-3-642-20877-5_43 |
| 出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。