Downloads: 78

Files in This Item:
File Description SizeFormat 
978-3-540-92182-0_9.pdf145.31 kBAdobe PDFView/Open
Title: Improving the Competitive Ratio of the Online OVSF Code Assignment Problem
Authors: Miyazaki, Shuichi  kyouindb  KAKEN_id  orcid https://orcid.org/0000-0003-0369-1970 (unconfirmed)
Okamoto, Kazuya  kyouindb  KAKEN_id  orcid https://orcid.org/0000-0002-9079-2253 (unconfirmed)
Author's alias: 宮崎, 修一
岡本, 和也
Keywords: 5369
Issue Date: 2008
Publisher: Springer Berlin Heidelberg
Journal title: Lecture Notes in Computer Science
Start page: 64
End page: 76
Abstract: 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 arbitrary ε> 0.
Description: 'Algorithms and Computation' 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008. Proceedings
Rights: The final publication is available at Springer via https://doi.org/10.1007/978-3-540-92182-0_9
This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。
URI: http://hdl.handle.net/2433/226948
DOI(Published Version): 10.1007/978-3-540-92182-0_9
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks


Export Format: 


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.