File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A constant-competitive algorithm for online OVSF code assignment

TitleA constant-competitive algorithm for online OVSF code assignment
Authors
KeywordsCompetitive analysis
Lower bounds
Online algorithms
Wideband code-division multiple-access
Issue Date2010
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
Citation
Algorithmica (New York), 2010, v. 56 n. 1, p. 89-104 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 (where the cost is measured by the total number of assignments and reassignments used). Our algorithm improves 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 not determined. We also improve the lower bound of the problem from 3/2 to 5/3. © 2008 Springer Science+Business Media, LLC.
Persistent Identifierhttp://hdl.handle.net/10722/127350
ISSN
2015 Impact Factor: 0.795
2015 SCImago Journal Rankings: 0.898
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorTing, HFen_HK
dc.contributor.authorZhang, Yen_HK
dc.date.accessioned2010-10-31T13:20:29Z-
dc.date.available2010-10-31T13:20:29Z-
dc.date.issued2010en_HK
dc.identifier.citationAlgorithmica (New York), 2010, v. 56 n. 1, p. 89-104en_HK
dc.identifier.issn0178-4617en_HK
dc.identifier.urihttp://hdl.handle.net/10722/127350-
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 (where the cost is measured by the total number of assignments and reassignments used). Our algorithm improves 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 not determined. We also improve the lower bound of the problem from 3/2 to 5/3. © 2008 Springer Science+Business Media, LLC.en_HK
dc.languageengen_HK
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htmen_HK
dc.relation.ispartofAlgorithmica (New York)en_HK
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectCompetitive analysisen_HK
dc.subjectLower boundsen_HK
dc.subjectOnline algorithmsen_HK
dc.subjectWideband code-division multiple-accessen_HK
dc.titleA constant-competitive algorithm for online OVSF code assignmenten_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0178-4617&volume=56&issue=1&spage=89&epage=104&date=2010&atitle=A+constant-competitive+algorithm+for+online+OVSF+code+assignmenten_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.doi10.1007/s00453-008-9241-8en_HK
dc.identifier.scopuseid_2-s2.0-73349116559en_HK
dc.identifier.hkuros178822en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-73349116559&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume56en_HK
dc.identifier.issue1en_HK
dc.identifier.spage89en_HK
dc.identifier.epage104en_HK
dc.identifier.isiWOS:000273030500006-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.scopusauthoridZhang, Y=7601329213en_HK
dc.identifier.citeulike3643108-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats