Access count of this item: 65

Files in This Item:
File Description SizeFormat 
a2030953.pdf348.72 kBAdobe PDFView/Open
Title: Improving the Competitive Ratio of the Online OVSF Code Assignment Problem
Authors: Miyazaki, Shuichi  kyouindb  KAKEN_id
Okamoto, Kazuya  kyouindb  KAKEN_id
Author's alias: 宮崎, 修一
岡本, 和也
Keywords: online OVSF code assignment
online algorithm
competitive analysis
Issue Date: 17-Jul-2009
Publisher: MDPI AG
Journal title: Algorithms
Volume: 2
Issue: 3
Start page: 953
End page: 972
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 an arbitrary constant ε > 0.
Rights: © 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(Published Version): 10.3390/a2030953
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.