File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/s00453-008-9241-8
- Scopus: eid_2-s2.0-73349116559
- WOS: WOS:000273030500006
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: A constant-competitive algorithm for online OVSF code assignment
Title | A constant-competitive algorithm for online OVSF code assignment |
---|---|
Authors | |
Keywords | Competitive analysis Lower bounds Online algorithms Wideband code-division multiple-access |
Issue Date | 2010 |
Publisher | Springer 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? |
Abstract | Orthogonal 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 Identifier | http://hdl.handle.net/10722/127350 |
ISSN | 2023 Impact Factor: 0.9 2023 SCImago Journal Rankings: 0.905 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chin, FYL | en_HK |
dc.contributor.author | Ting, HF | en_HK |
dc.contributor.author | Zhang, Y | en_HK |
dc.date.accessioned | 2010-10-31T13:20:29Z | - |
dc.date.available | 2010-10-31T13:20:29Z | - |
dc.date.issued | 2010 | en_HK |
dc.identifier.citation | Algorithmica (New York), 2010, v. 56 n. 1, p. 89-104 | en_HK |
dc.identifier.issn | 0178-4617 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/127350 | - |
dc.description.abstract | Orthogonal 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.language | eng | en_HK |
dc.publisher | Springer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm | en_HK |
dc.relation.ispartof | Algorithmica (New York) | en_HK |
dc.rights | The original publication is available at www.springerlink.com | - |
dc.subject | Competitive analysis | en_HK |
dc.subject | Lower bounds | en_HK |
dc.subject | Online algorithms | en_HK |
dc.subject | Wideband code-division multiple-access | en_HK |
dc.title | A constant-competitive algorithm for online OVSF code assignment | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://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+assignment | en_HK |
dc.identifier.email | Chin, FYL:chin@cs.hku.hk | en_HK |
dc.identifier.email | Ting, HF:hfting@cs.hku.hk | en_HK |
dc.identifier.authority | Chin, FYL=rp00105 | en_HK |
dc.identifier.authority | Ting, HF=rp00177 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1007/s00453-008-9241-8 | en_HK |
dc.identifier.scopus | eid_2-s2.0-73349116559 | en_HK |
dc.identifier.hkuros | 178822 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-73349116559&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 56 | en_HK |
dc.identifier.issue | 1 | en_HK |
dc.identifier.spage | 89 | en_HK |
dc.identifier.epage | 104 | en_HK |
dc.identifier.isi | WOS:000273030500006 | - |
dc.publisher.place | United States | en_HK |
dc.identifier.scopusauthorid | Chin, FYL=7005101915 | en_HK |
dc.identifier.scopusauthorid | Ting, HF=7005654198 | en_HK |
dc.identifier.scopusauthorid | Zhang, Y=7601329213 | en_HK |
dc.identifier.citeulike | 3643108 | - |
dc.identifier.issnl | 0178-4617 | - |