ダウンロード数: 293
このアイテムのファイル:
| ファイル | 記述 | サイズ | フォーマット | |
|---|---|---|---|---|
| j.ipl.2014.06.013.pdf | 61.02 kB | Adobe PDF | 見る/開く |
| タイトル: | On the advice complexity of online bipartite matching and online stable marriage |
| 著者: | Miyazaki, Shuichi   https://orcid.org/0000-0003-0369-1970 (unconfirmed) |
| 著者名の別形: | 宮崎, 修一 |
| キーワード: | On-line algorithms Advice complexity Bipartite matching Stable marriage |
| 発行日: | Dec-2014 |
| 出版者: | Elsevier BV |
| 誌名: | Information Processing Letters |
| 巻: | 114 |
| 号: | 12 |
| 開始ページ: | 714 |
| 終了ページ: | 717 |
| 抄録: | In this paper, we study the advice complexity of the online bipartite matching problem and the online stable marriage problem. We show that for both problems, ⌈log2(n!)⌉ bits of advice are necessary and sufficient for a deterministic online algorithm to be optimal, where n denotes the number of vertices in one bipartition in the former problem, and the number of men in the latter. |
| 著作権等: | © 2014. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ The full-text file will be made open to the public on 01 December 2016 in accordance with publisher's 'Terms and Conditions for Self-Archiving'. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 This is not the published version. Please cite only the published version. |
| URI: | http://hdl.handle.net/2433/226931 |
| DOI(出版社版): | 10.1016/j.ipl.2014.06.013 |
| 出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。