File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Article: Absolute and asymptotic bounds for online frequency allocation in cellular networks
  • Basic View
  • Metadata View
  • XML View
TitleAbsolute and asymptotic bounds for online frequency allocation in cellular networks
 
AuthorsChan, JWT1
Chin, FYL2
Ye, D3
Zhang, Y2
 
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
 
CitationAlgorithmica (New York), 2010, v. 58 n. 2, p. 498-515 [How to Cite?]
DOI: http://dx.doi.org/10.1007/s00453-009-9279-2
 
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.
 
ISSN0178-4617
2013 Impact Factor: 0.567
 
DOIhttp://dx.doi.org/10.1007/s00453-009-9279-2
 
ISI Accession Number IDWOS:000279681700013
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).

 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorChan, JWT
 
dc.contributor.authorChin, FYL
 
dc.contributor.authorYe, D
 
dc.contributor.authorZhang, Y
 
dc.date.accessioned2010-12-23T08:45:07Z
 
dc.date.available2010-12-23T08:45:07Z
 
dc.date.issued2010
 
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.
 
dc.description.natureLink_to_subscribed_fulltext
 
dc.identifier.citationAlgorithmica (New York), 2010, v. 58 n. 2, p. 498-515 [How to Cite?]
DOI: http://dx.doi.org/10.1007/s00453-009-9279-2
 
dc.identifier.citeulike3989277
 
dc.identifier.doihttp://dx.doi.org/10.1007/s00453-009-9279-2
 
dc.identifier.eissn1432-0541
 
dc.identifier.epage515
 
dc.identifier.hkuros178318
 
dc.identifier.isiWOS:000279681700013
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).

 
dc.identifier.issn0178-4617
2013 Impact Factor: 0.567
 
dc.identifier.issue2
 
dc.identifier.openurl
 
dc.identifier.scopuseid_2-s2.0-77955663788
 
dc.identifier.spage498
 
dc.identifier.urihttp://hdl.handle.net/10722/129982
 
dc.identifier.volume58
 
dc.languageeng
 
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
 
dc.publisher.placeUnited States
 
dc.relation.ispartofAlgorithmica (New York)
 
dc.relation.referencesReferences in Scopus
 
dc.rightsThe original publication is available at www.springerlink.com
 
dc.subjectCellular networks
 
dc.subjectCompetitive analysis
 
dc.subjectFrequency allocation
 
dc.subjectMulticoloring
 
dc.subjectOnline algorithms
 
dc.titleAbsolute and asymptotic bounds for online frequency allocation in cellular networks
 
dc.typeArticle
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Chan, JWT</contributor.author>
<contributor.author>Chin, FYL</contributor.author>
<contributor.author>Ye, D</contributor.author>
<contributor.author>Zhang, Y</contributor.author>
<date.accessioned>2010-12-23T08:45:07Z</date.accessioned>
<date.available>2010-12-23T08:45:07Z</date.available>
<date.issued>2010</date.issued>
<identifier.citation>Algorithmica (New York), 2010, v. 58 n. 2, p. 498-515</identifier.citation>
<identifier.issn>0178-4617</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/129982</identifier.uri>
<description.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 &#967;-colorable networks, which is a generalization of the (3-colorable) cellular networks, we present a (&#967;+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. &#169; 2009 Springer Science+Business Media, LLC.</description.abstract>
<language>eng</language>
<publisher>Springer New York LLC. The Journal&apos;s web site is located at http://link.springer.de/link/service/journals/00453/index.htm</publisher>
<relation.ispartof>Algorithmica (New York)</relation.ispartof>
<rights>The original publication is available at www.springerlink.com</rights>
<subject>Cellular networks</subject>
<subject>Competitive analysis</subject>
<subject>Frequency allocation</subject>
<subject>Multicoloring</subject>
<subject>Online algorithms</subject>
<title>Absolute and asymptotic bounds for online frequency allocation in cellular networks</title>
<type>Article</type>
<identifier.openurl>http://library.hku.hk:4550/resserv?sid=HKU:IR&amp;issn=0178-4617&amp;volume=58&amp;issue=2&amp;spage=498&amp;epage=515&amp;date=2010&amp;atitle=Absolute+and+asymptotic+bounds+for+online+frequency+allocation+in+cellular+networks</identifier.openurl>
<description.nature>Link_to_subscribed_fulltext</description.nature>
<identifier.doi>10.1007/s00453-009-9279-2</identifier.doi>
<identifier.scopus>eid_2-s2.0-77955663788</identifier.scopus>
<identifier.hkuros>178318</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-77955663788&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>58</identifier.volume>
<identifier.issue>2</identifier.issue>
<identifier.spage>498</identifier.spage>
<identifier.epage>515</identifier.epage>
<identifier.eissn>1432-0541</identifier.eissn>
<identifier.isi>WOS:000279681700013</identifier.isi>
<publisher.place>United States</publisher.place>
<identifier.citeulike>3989277</identifier.citeulike>
</item>
Author Affiliations
  1. King's College London
  2. The University of Hong Kong
  3. Zhejiang University