{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:40:48Z","timestamp":1760244048088,"version":"build-2065373602"},"reference-count":12,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2009,7,17]],"date-time":"2009-07-17T00:00:00Z","timestamp":1247788800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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 \u2015 \u03b5 for an arbitrary constant \u03b5 &gt; 0.<\/jats:p>","DOI":"10.3390\/a2030953","type":"journal-article","created":{"date-parts":[[2009,7,17]],"date-time":"2009-07-17T12:13:46Z","timestamp":1247832826000},"page":"953-972","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Improving the Competitive Ratio of the Online OVSF Code Assignment Problem"],"prefix":"10.3390","volume":"2","author":[{"given":"Shuichi","family":"Miyazaki","sequence":"first","affiliation":[{"name":"Academic Center for Computing and Media Studies, Kyoto University, Yoshida Honmachi, Sakyo-ku, Kyoto 606-8501, Japan"}]},{"given":"Kazuya","family":"Okamoto","sequence":"additional","affiliation":[{"name":"Graduate School of Informatics, Kyoto University, Yoshida Honmachi, Sakyo-ku, Kyoto 606-8501, Japan"}]}],"member":"1968","published-online":{"date-parts":[[2009,7,17]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Holma, H., and Toskala, A. (2001). WCDMA for UMTS, Wiley.","DOI":"10.1002\/0470870982"},{"key":"ref_2","unstructured":"Laiho, J., Wacker, A., and Novosad, T. (2002). Radio Network Planning and Optimisation for UMTS, Wiley."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1049\/el:19970022","article-title":"Tree-structured generation of orthogonal spreading codes with different lengths for forward link of DS-CDMA mobile radio","volume":"33","author":"Adachi","year":"1997","journal-title":"Electronics Letters"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/s00453-006-0188-3","article-title":"An algorithmic view on OVSF code assignment","volume":"47","author":"Erlebach","year":"2007","journal-title":"Algorithmica"},{"key":"ref_5","first-page":"546","article-title":"Online bandwidth allocation","volume":"LNCS 4698","author":"Katreniak","year":"2007","journal-title":"Proc. of The 16th Annual European Symposium on Algorithms (ESA)"},{"key":"ref_6","first-page":"452","article-title":"A constant-competitive algorithm for online OVSF code assignment","volume":"LNCS 4835","author":"Chin","year":"2007","journal-title":"Proc. of The 18th International Symposium on Algorithms and Computation (ISAAC)"},{"key":"ref_7","first-page":"191","article-title":"Online OVSF code assignment with resource augmentation","volume":"LNCS 4508","author":"Chin","year":"2007","journal-title":"Proc. of The 3rd International Conference on Algorithmic Aspects in Information and Management (AAIM)"},{"key":"ref_8","first-page":"358","article-title":"Online Tree Node Assignment with Resource Augmentation","volume":"LNCS 5609","author":"Chan","year":"2009","journal-title":"Proc. of The 15th International Computing and Combinatorics Conference (COCOON)"},{"key":"ref_9","first-page":"142","article-title":"Stochastic Methods for Dynamic OVSF Code Assignment in 3G Networks","volume":"LNCS 4665","author":"Karakoc","year":"2007","journal-title":"Proc. of The 4th International Symposium on Stochastic Algorithms: Foundations and Applications (SAGA)"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1429","DOI":"10.1109\/49.864008","article-title":"Dynamic assignment of orthogonal variable-spreading-factor codes in W-CDMA","volume":"18","author":"Minn","year":"2000","journal-title":"IEEE Journal on Selected Areas in Communications"},{"key":"ref_11","unstructured":"Erlebach, T., Jacob, R., and Tomamichel, M. Algorithmische Aspekte von OVSF code assignment mit Schwerpunkt auf offline code assignment, Student thesis as ETH Z\u00fcrich."},{"key":"ref_12","unstructured":"Chin, F.Y.L., Ting, H.F., and Zhang, Y. Constant-Competitive Tree Node Assignment, manuscript."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/2\/3\/953\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T22:10:46Z","timestamp":1760220646000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/2\/3\/953"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7,17]]},"references-count":12,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2009,9]]}},"alternative-id":["a2030953"],"URL":"https:\/\/doi.org\/10.3390\/a2030953","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2009,7,17]]}}}