ダウンロード数: 164
このアイテムのファイル:
| ファイル | 記述 | サイズ | フォーマット | |
|---|---|---|---|---|
| 978-3-540-27810-8_30.pdf | 216.39 kB | Adobe PDF | 見る/開く |
| タイトル: | A (2-c log N/N)–Approximation Algorithm for the Stable Marriage Problem |
| 著者: | Iwama, Kazuo Miyazaki, Shuichi Okamoto, Kazuya   https://orcid.org/0000-0002-9079-2253 (unconfirmed) |
| 著者名の別形: | 岩間, 一雄 宮崎, 修一 岡本, 和也 |
| 発行日: | 2004 |
| 出版者: | Springer Berlin Heidelberg |
| 誌名: | Lecture Notes in Computer Science |
| 巻: | 3111 |
| 開始ページ: | 349 |
| 終了ページ: | 361 |
| 抄録: | We propose an approximation algorithm for the problem of finding a maximum stable matching when both ties and unacceptable partners are allowed in preference lists. Our algorithm achieves the approximation ratio (2-c log N/N) for an arbitrarily positive constant c, where N denotes the number of men in an input. This improves the trivial approximation ratio of two. |
| 記述: | ’Algorithm Theory - SWAT 2004’ 9th Scandinavian Workshop on Algorithm Theory, Humlebæk, Denmark, July 8-10, 2004. Proceedings |
| 著作権等: | The final publication is available at Springer via https://doi.org/10.1007/978-3-540-27810-8_30 この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 This is not the published version. Please cite only the published version. |
| URI: | http://hdl.handle.net/2433/227016 |
| DOI(出版社版): | 10.1007/978-3-540-27810-8_30 |
| 出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。