File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Absolute and asymptotic bounds for online frequency allocation in cellular networks

TitleAbsolute and asymptotic bounds for online frequency allocation in cellular networks
Authors
KeywordsCellular networks
Competitive analysis
Frequency allocation
Multicoloring
Online algorithms
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. 58 n. 2, p. 498-515 How to Cite?
Abstract
Given a cellular (mobile telephone) network, whose geographical coverage area is divided into hexagonal cells, phone calls are serviced by assigning frequencies to them so that no two calls emanating from the same or neighboring cells are assigned the same frequency. Assuming an online arrival of calls, the goal is to minimize the span of frequencies used to serve all of the calls. By first considering χ-colorable networks, which is a generalization of the (3-colorable) cellular networks, we present a (χ+1)/2-competitive online algorithm. This algorithm, when applied to cellular networks, is effectively a positive solution to the open problem posed in (Caragiannis et al. in Theory Comput. Syst. 35(5):521-543, 2002) Does a 2-competitive online algorithm exist for frequency allocation in cellular networks? We further prove a matching lower bound, which shows that our 2-competitive algorithm is optimal. We discover that an interesting phenomenon occurs for the online frequency allocation problem when the number of calls considered becomes large: previously-derived optimal bounds on competitive ratios no longer hold true. For cellular networks, we show a new asymptotic lower and upper bounds of 1.5 and 1.9126, respectively, which breaks through the optimal bound of 2 shown above. © 2009 Springer Science+Business Media, LLC.
Persistent Identifierhttp://hdl.handle.net/10722/129982
ISSN
2013 Impact Factor: 0.567
ISI Accession Number ID
Funding AgencyGrant Number
Hong Kong RGCHKU 7113/07E
NSFC10601048
National Natural Science Fund60496321
Funding Information:

F.Y.L. Chin was supported in parts by Hong Kong RGC Research Grant HKU 7113/07E. D. Ye was supported in parts by grant NSFC (10601048). Y. Zhang was supported in parts by National Natural Science Fund (grant no. 60496321).

References

 

Author Affiliations
  1. King's College London
  2. The University of Hong Kong
  3. Zhejiang University
DC FieldValueLanguage
dc.contributor.authorChan, JWTen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorYe, Den_HK
dc.contributor.authorZhang, Yen_HK
dc.date.accessioned2010-12-23T08:45:07Z-
dc.date.available2010-12-23T08:45:07Z-
dc.date.issued2010en_HK
dc.identifier.citationAlgorithmica (New York), 2010, v. 58 n. 2, p. 498-515en_HK
dc.identifier.issn0178-4617en_HK
dc.identifier.urihttp://hdl.handle.net/10722/129982-
dc.description.abstractGiven a cellular (mobile telephone) network, whose geographical coverage area is divided into hexagonal cells, phone calls are serviced by assigning frequencies to them so that no two calls emanating from the same or neighboring cells are assigned the same frequency. Assuming an online arrival of calls, the goal is to minimize the span of frequencies used to serve all of the calls. By first considering χ-colorable networks, which is a generalization of the (3-colorable) cellular networks, we present a (χ+1)/2-competitive online algorithm. This algorithm, when applied to cellular networks, is effectively a positive solution to the open problem posed in (Caragiannis et al. in Theory Comput. Syst. 35(5):521-543, 2002) Does a 2-competitive online algorithm exist for frequency allocation in cellular networks? We further prove a matching lower bound, which shows that our 2-competitive algorithm is optimal. We discover that an interesting phenomenon occurs for the online frequency allocation problem when the number of calls considered becomes large: previously-derived optimal bounds on competitive ratios no longer hold true. For cellular networks, we show a new asymptotic lower and upper bounds of 1.5 and 1.9126, respectively, which breaks through the optimal bound of 2 shown above. © 2009 Springer Science+Business Media, LLC.en_HK
dc.languageengen_US
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.comen_US
dc.subjectCellular networksen_HK
dc.subjectCompetitive analysisen_HK
dc.subjectFrequency allocationen_HK
dc.subjectMulticoloringen_HK
dc.subjectOnline algorithmsen_HK
dc.titleAbsolute and asymptotic bounds for online frequency allocation in cellular networksen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0178-4617&volume=58&issue=2&spage=498&epage=515&date=2010&atitle=Absolute+and+asymptotic+bounds+for+online+frequency+allocation+in+cellular+networksen_US
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/s00453-009-9279-2en_HK
dc.identifier.scopuseid_2-s2.0-77955663788en_HK
dc.identifier.hkuros178318en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-77955663788&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume58en_HK
dc.identifier.issue2en_HK
dc.identifier.spage498en_HK
dc.identifier.epage515en_HK
dc.identifier.eissn1432-0541-
dc.identifier.isiWOS:000279681700013-
dc.publisher.placeUnited Statesen_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.citeulike3989277-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats