ダウンロード数: 187
このアイテムのファイル:
| ファイル | 記述 | サイズ | フォーマット | |
|---|---|---|---|---|
| a2030953.pdf | 348.72 kB | Adobe PDF | 見る/開く |
| タイトル: | Improving the Competitive Ratio of the Online OVSF Code Assignment Problem |
| 著者: | Miyazaki, Shuichi   https://orcid.org/0000-0003-0369-1970 (unconfirmed)Okamoto, Kazuya https://orcid.org/0000-0002-9079-2253 (unconfirmed) |
| 著者名の別形: | 宮崎, 修一 岡本, 和也 |
| キーワード: | online OVSF code assignment online algorithm competitive analysis |
| 発行日: | 17-Jul-2009 |
| 出版者: | MDPI AG |
| 誌名: | Algorithms |
| 巻: | 2 |
| 号: | 3 |
| 開始ページ: | 953 |
| 終了ページ: | 972 |
| 抄録: | Online OVSF code assignment has an important application to wireless communications. Recently, this problem was formally modeled as an online problem, and performances of online algorithms have been analyzed by the competitive analysis. The previous best upper and lower bounds on the competitive ratio were 10 and 5/3, respectively. In this paper, we improve them to 7 and 2, respectively. We also show that our analysis for the upper bound is tight by giving an input sequence for which the competitive ratio of our algorithm is 7 ― ε for an arbitrary constant ε > 0. |
| 著作権等: | © 2009 by the authors; licensee Molecular Diversity Preservation International, Basel, Switzerland. This is an open access article distributed under the Creative Commons Attribution License (CC BY 3.0). |
| URI: | http://hdl.handle.net/2433/226991 |
| DOI(出版社版): | 10.3390/a2030953 |
| 出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。