File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: A constant-competitive algorithm for online OVSF code assignment

TitleA constant-competitive algorithm for online OVSF code assignment
Authors
Issue Date2007
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 18th International Symposium on Algorithms and Computation (ISAAC 2007), Sendai, Japan, 17-19 December 2007. In Lecture Notes In Computer Science, 2007, v. 4835, p. 452-463 How to Cite?
AbstractOrthogonal Variable Spreading Factor (OVSF) code assignment is a fundamental problem in Wideband Code-Division Multiple-Access (W-CDMA) systems, which plays an important role in third generation mobile communications. In the OVSF problem, codes must be assigned to incoming call requests with different data rate requirements, in such a way that they are mutually orthogonal with respect to an OVSF code tree. An OVSF code tree is a complete binary tree in which each node represents a code associated with the combined bandwidths of its two children. To be mutually orthogonal, each leaf-to-root path must contain at most one assigned code. In this paper, we focus on the online version of the OVSF code assignment problem and give a 10-competitive algorithm, improving the previous O(h)-competitive result, where h is the height of the code tree, and also another recent constant-competitive result, where the competitive ratio is only constant under amortized analysis and the constant is never determined. Finally, we also improve the lower bound of the problem from 3/2 to 5/3. © Springer-Verlag Berlin Heidelberg 2007.
Persistent Identifierhttp://hdl.handle.net/10722/93238
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorTing, HFen_HK
dc.contributor.authorZhang, Yen_HK
dc.date.accessioned2010-09-25T14:55:04Z-
dc.date.available2010-09-25T14:55:04Z-
dc.date.issued2007en_HK
dc.identifier.citationThe 18th International Symposium on Algorithms and Computation (ISAAC 2007), Sendai, Japan, 17-19 December 2007. In Lecture Notes In Computer Science, 2007, v. 4835, p. 452-463en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93238-
dc.description.abstractOrthogonal Variable Spreading Factor (OVSF) code assignment is a fundamental problem in Wideband Code-Division Multiple-Access (W-CDMA) systems, which plays an important role in third generation mobile communications. In the OVSF problem, codes must be assigned to incoming call requests with different data rate requirements, in such a way that they are mutually orthogonal with respect to an OVSF code tree. An OVSF code tree is a complete binary tree in which each node represents a code associated with the combined bandwidths of its two children. To be mutually orthogonal, each leaf-to-root path must contain at most one assigned code. In this paper, we focus on the online version of the OVSF code assignment problem and give a 10-competitive algorithm, improving the previous O(h)-competitive result, where h is the height of the code tree, and also another recent constant-competitive result, where the competitive ratio is only constant under amortized analysis and the constant is never determined. Finally, we also improve the lower bound of the problem from 3/2 to 5/3. © Springer-Verlag Berlin Heidelberg 2007.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Scienceen_HK
dc.titleA constant-competitive algorithm for online OVSF code assignmenten_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChin, FYL: chin@cs.hku.hken_HK
dc.identifier.emailTing, HF: hfting@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-38149051285en_HK
dc.identifier.hkuros140902en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-38149051285&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume4835en_HK
dc.identifier.spage452en_HK
dc.identifier.epage463en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.scopusauthoridZhang, Y=51462337000en_HK
dc.customcontrol.immutablesml 160111 - amend-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats