File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Greedy online frequency allocation in cellular networks

TitleGreedy online frequency allocation in cellular networks
Authors
KeywordsCellular network
Competitive analysis
Frequency allocation
Greedy algorithm
On-line algorithms
Issue Date2007
PublisherElsevier 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?
AbstractThe 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 Identifierhttp://hdl.handle.net/10722/89145
ISSN
2015 Impact Factor: 0.605
2015 SCImago Journal Rankings: 0.698
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChan, JWTen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorYe, Den_HK
dc.contributor.authorZhang, Yen_HK
dc.contributor.authorZhu, Hen_HK
dc.date.accessioned2010-09-06T09:52:57Z-
dc.date.available2010-09-06T09:52:57Z-
dc.date.issued2007en_HK
dc.identifier.citationInformation Processing Letters, 2007, v. 102 n. 2-3, p. 55-61en_HK
dc.identifier.issn0020-0190en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89145-
dc.description.abstractThe 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.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/iplen_HK
dc.relation.ispartofInformation Processing Lettersen_HK
dc.rightsInformation Processing Letters. Copyright © Elsevier BV.en_HK
dc.subjectCellular networken_HK
dc.subjectCompetitive analysisen_HK
dc.subjectFrequency allocationen_HK
dc.subjectGreedy algorithmen_HK
dc.subjectOn-line algorithmsen_HK
dc.titleGreedy online frequency allocation in cellular networksen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://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+Networksen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/j.ipl.2006.11.015en_HK
dc.identifier.scopuseid_2-s2.0-33847288729en_HK
dc.identifier.hkuros126292en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33847288729&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume102en_HK
dc.identifier.issue2-3en_HK
dc.identifier.spage55en_HK
dc.identifier.epage61en_HK
dc.identifier.isiWOS:000244994100003-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridChan, JWT=16021445200en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridYe, D=16023572800en_HK
dc.identifier.scopusauthoridZhang, Y=7601329213en_HK
dc.identifier.scopusauthoridZhu, H=7404663553en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats