File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1016/j.ipl.2006.11.015
- Scopus: eid_2-s2.0-33847288729
- WOS: WOS:000244994100003
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Greedy online frequency allocation in cellular networks
Title | Greedy online frequency allocation in cellular networks |
---|---|
Authors | |
Keywords | Cellular network Competitive analysis Frequency allocation Greedy algorithm On-line algorithms |
Issue Date | 2007 |
Publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/ipl |
Citation | Information Processing Letters, 2007, v. 102 n. 2-3, p. 55-61 How to Cite? |
Abstract | The online frequency allocation problem for cellular networks has been well studied in these years. Given a mobile telephone network, whose geographical coverage area is divided into cells, phone calls are served by assigning frequencies to them, and no two calls emanating from the same or neighboring cells are assigned the same frequency. Assuming an online setting that the calls arrive one by one, the problem is to minimize the span of the frequencies used. In this paper, we study the greedy approach for the online frequency allocation problem, which assigns the minimal available frequency to a new call so that the call does not interfere with calls of the same cell or neighboring cells. If the calls have infinite duration, the competitive ratio of greedy algorithm has a tight upper bound of 17/7, which closes the gap of [17 / 7, 2.5) in [I. Caragiannis, C. Kaklamanis, E. Papaioannou, Efficient on-line frequency allocation and call control in cellular networks, Theory Comput. Syst. 35 (5) (2002) 521-543. A preliminary version of the paper appeared in SPAA 2000]. If the calls have finite duration, i.e., each call may be terminated at some time, the competitive ratio of the greedy algorithm has a tight upper bound of 3. © 2006 Elsevier B.V. All rights reserved. |
Persistent Identifier | http://hdl.handle.net/10722/89145 |
ISSN | 2023 Impact Factor: 0.7 2023 SCImago Journal Rankings: 0.404 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, JWT | en_HK |
dc.contributor.author | Chin, FYL | en_HK |
dc.contributor.author | Ye, D | en_HK |
dc.contributor.author | Zhang, Y | en_HK |
dc.contributor.author | Zhu, H | en_HK |
dc.date.accessioned | 2010-09-06T09:52:57Z | - |
dc.date.available | 2010-09-06T09:52:57Z | - |
dc.date.issued | 2007 | en_HK |
dc.identifier.citation | Information Processing Letters, 2007, v. 102 n. 2-3, p. 55-61 | en_HK |
dc.identifier.issn | 0020-0190 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/89145 | - |
dc.description.abstract | The online frequency allocation problem for cellular networks has been well studied in these years. Given a mobile telephone network, whose geographical coverage area is divided into cells, phone calls are served by assigning frequencies to them, and no two calls emanating from the same or neighboring cells are assigned the same frequency. Assuming an online setting that the calls arrive one by one, the problem is to minimize the span of the frequencies used. In this paper, we study the greedy approach for the online frequency allocation problem, which assigns the minimal available frequency to a new call so that the call does not interfere with calls of the same cell or neighboring cells. If the calls have infinite duration, the competitive ratio of greedy algorithm has a tight upper bound of 17/7, which closes the gap of [17 / 7, 2.5) in [I. Caragiannis, C. Kaklamanis, E. Papaioannou, Efficient on-line frequency allocation and call control in cellular networks, Theory Comput. Syst. 35 (5) (2002) 521-543. A preliminary version of the paper appeared in SPAA 2000]. If the calls have finite duration, i.e., each call may be terminated at some time, the competitive ratio of the greedy algorithm has a tight upper bound of 3. © 2006 Elsevier B.V. All rights reserved. | en_HK |
dc.language | eng | en_HK |
dc.publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/ipl | en_HK |
dc.relation.ispartof | Information Processing Letters | en_HK |
dc.rights | Information Processing Letters. Copyright © Elsevier BV. | en_HK |
dc.subject | Cellular network | en_HK |
dc.subject | Competitive analysis | en_HK |
dc.subject | Frequency allocation | en_HK |
dc.subject | Greedy algorithm | en_HK |
dc.subject | On-line algorithms | en_HK |
dc.title | Greedy online frequency allocation in cellular networks | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0020-0190&volume=102&issue=2-3&spage=55&epage=61&date=2007&atitle=Greedy+Online+Frequency+Allocation+in+Cellular+Networks | en_HK |
dc.identifier.email | Chin, FYL:chin@cs.hku.hk | en_HK |
dc.identifier.authority | Chin, FYL=rp00105 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1016/j.ipl.2006.11.015 | en_HK |
dc.identifier.scopus | eid_2-s2.0-33847288729 | en_HK |
dc.identifier.hkuros | 126292 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-33847288729&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 102 | en_HK |
dc.identifier.issue | 2-3 | en_HK |
dc.identifier.spage | 55 | en_HK |
dc.identifier.epage | 61 | en_HK |
dc.identifier.isi | WOS:000244994100003 | - |
dc.publisher.place | Netherlands | en_HK |
dc.identifier.scopusauthorid | Chan, JWT=16021445200 | en_HK |
dc.identifier.scopusauthorid | Chin, FYL=7005101915 | en_HK |
dc.identifier.scopusauthorid | Ye, D=16023572800 | en_HK |
dc.identifier.scopusauthorid | Zhang, Y=7601329213 | en_HK |
dc.identifier.scopusauthorid | Zhu, H=7404663553 | en_HK |
dc.identifier.issnl | 0020-0190 | - |