Improving the Competitive Ratio of the Online OVSF Code Assignment Problem

• 宮崎, 修一

  Academic Center for Computing and Media StudiesKyoto University

• 岡本, 和也

  Graduate School of InformaticsKyoto University

抄録

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.

'Algorithms and Computation' 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008. Proceedings

収録刊行物

• Lecture Notes in Computer Science

  Lecture Notes in Computer Science 64-76, 2008

  Springer Berlin Heidelberg

キーワード

• 5369

詳細情報

• CRID: 1050845760779568000
• NII論文ID: 120006338074
• ISSN: 03029743
• HANDLE: 2433/226948
• 本文言語コード: en
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles