Improving the Competitive Ratio of the Online OVSF Code Assignment Problem
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 rat...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2009-07-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1999-4893/2/3/953/ |
| _version_ | 1811252453320949760 |
|---|---|
| author | Shuichi Miyazaki Kazuya Okamoto |
| author_facet | Shuichi Miyazaki Kazuya Okamoto |
| author_sort | Shuichi Miyazaki |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-12T16:34:50Z |
| format | Article |
| id | doaj.art-97a0554f51cc469287c92740c30ddaca |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-04-12T16:34:50Z |
| publishDate | 2009-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-97a0554f51cc469287c92740c30ddaca2022-12-22T03:25:01ZengMDPI AGAlgorithms1999-48932009-07-012395397210.3390/a2030953Improving the Competitive Ratio of the Online OVSF Code Assignment ProblemShuichi MiyazakiKazuya OkamotoOnline 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.http://www.mdpi.com/1999-4893/2/3/953/online OVSF code assignmentonline algorithmcompetitive analysis |
| spellingShingle | Shuichi Miyazaki Kazuya Okamoto Improving the Competitive Ratio of the Online OVSF Code Assignment Problem Algorithms online OVSF code assignment online algorithm competitive analysis |
| title | Improving the Competitive Ratio of the Online OVSF Code Assignment Problem |
| title_full | Improving the Competitive Ratio of the Online OVSF Code Assignment Problem |
| title_fullStr | Improving the Competitive Ratio of the Online OVSF Code Assignment Problem |
| title_full_unstemmed | Improving the Competitive Ratio of the Online OVSF Code Assignment Problem |
| title_short | Improving the Competitive Ratio of the Online OVSF Code Assignment Problem |
| title_sort | improving the competitive ratio of the online ovsf code assignment problem |
| topic | online OVSF code assignment online algorithm competitive analysis |
| url | http://www.mdpi.com/1999-4893/2/3/953/ |
| work_keys_str_mv | AT shuichimiyazaki improvingthecompetitiveratiooftheonlineovsfcodeassignmentproblem AT kazuyaokamoto improvingthecompetitiveratiooftheonlineovsfcodeassignmentproblem |