Improving the Competitive Ratio of the Online OVSF Code Assignment Problem*

Algorithms

Shuichi Miyazaki¹ 

[1] Academic Center for Computing and Media Studies, Kyoto University, Yoshida Honmachi, Sakyo-ku, Kyoto 606-8501, Japan; E-mails:

关键词: online OVSF code assignment;    online algorithm;    competitive analysis;   

DOI  :  10.3390/a2030953

来源: mdpi

【 摘 要 】

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 .

【 授权许可】

CC BY   
© 2009 by the authors; licensee Molecular Diversity Preservation International, Basel, Switzerland.