File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1007/11940128_8
 Scopus: eid_2s2.077249095123
 Find via
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Frequency allocation problems for linear cellular networks
Title  Frequency allocation problems for linear cellular networks 

Authors  
Issue Date  2006 
Publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ 
Citation  The 17th International Symposium on Algorithms and Computation (ISAAC 2006), Kolkata, India, 1820 December 2006. In Lecture Notes In Computer Science, 2006, v. 4288, p. 6170 How to Cite? 
Abstract  We study the online frequency allocation problem for wireless linear (highway) cellular networks, where the geographical coverage area is divided into cells aligned in a line. Calls arrive over time and are served by assigning frequencies to them, and no two calls emanating from the same cell or neighboring cells are assigned the same frequency. The objective is to minimize the span of frequencies used. In this paper we consider the problem with or without the assumption that calls have infinite duration. If there is the assumption, we propose an algorithm with absolute competitive ratio of 3/2 and asymptotic competitive ratio of 1.382. The lower bounds are also given: the absolute one is 3/2 and the asymptotic one is 4/3. Thus, our algorithm with absolute ratio of 3/2 is best possible. We also prove that the Greedy algorithm is 3/2competitive in both the absolute and asymptotic cases. For the problem without the assumption, i.e. calls may terminate at arbitrary time, we give the lower bounds for the competitive ratios: the absolute one is 5/3 and the asymptotic one is 14/9. We propose an optimal online algorithm with both competitive ratio of 5/3, which is better than the Greedy algorithm, with both competitive ratios 2. © 2006 SpringerVerlag Berlin/Heidelberg. 
Persistent Identifier  http://hdl.handle.net/10722/93145 
ISSN  2005 Impact Factor: 0.402 2015 SCImago Journal Rankings: 0.252 
References 
DC Field  Value  Language 

dc.contributor.author  Chan, WT  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  20100925T14:52:15Z   
dc.date.available  20100925T14:52:15Z   
dc.date.issued  2006  en_HK 
dc.identifier.citation  The 17th International Symposium on Algorithms and Computation (ISAAC 2006), Kolkata, India, 1820 December 2006. In Lecture Notes In Computer Science, 2006, v. 4288, p. 6170  en_HK 
dc.identifier.issn  03029743   
dc.identifier.uri  http://hdl.handle.net/10722/93145   
dc.description.abstract  We study the online frequency allocation problem for wireless linear (highway) cellular networks, where the geographical coverage area is divided into cells aligned in a line. Calls arrive over time and are served by assigning frequencies to them, and no two calls emanating from the same cell or neighboring cells are assigned the same frequency. The objective is to minimize the span of frequencies used. In this paper we consider the problem with or without the assumption that calls have infinite duration. If there is the assumption, we propose an algorithm with absolute competitive ratio of 3/2 and asymptotic competitive ratio of 1.382. The lower bounds are also given: the absolute one is 3/2 and the asymptotic one is 4/3. Thus, our algorithm with absolute ratio of 3/2 is best possible. We also prove that the Greedy algorithm is 3/2competitive in both the absolute and asymptotic cases. For the problem without the assumption, i.e. calls may terminate at arbitrary time, we give the lower bounds for the competitive ratios: the absolute one is 5/3 and the asymptotic one is 14/9. We propose an optimal online algorithm with both competitive ratio of 5/3, which is better than the Greedy algorithm, with both competitive ratios 2. © 2006 SpringerVerlag Berlin/Heidelberg.   
dc.language  eng  en_HK 
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/   
dc.relation.ispartof  Lecture Notes in Computer Science  en_HK 
dc.title  Frequency allocation problems for linear cellular networks  en_HK 
dc.type  Conference_Paper  en_HK 
dc.identifier.email  Chin, FYL: chin@cs.hku.hk  en_HK 
dc.identifier.email  Ye, D: yedeshi@cs.hku.hk  en_HK 
dc.identifier.email  Zhang, Y: yzhang.hku@cs.hku.hk  en_HK 
dc.identifier.authority  Chin, FYL=rp00105  en_HK 
dc.description.nature  link_to_subscribed_fulltext   
dc.identifier.doi  10.1007/11940128_8   
dc.identifier.scopus  eid_2s2.077249095123   
dc.identifier.hkuros  128855  en_HK 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.077249095123&selection=ref&src=s&origin=recordpage   
dc.identifier.volume  4288   
dc.identifier.spage  61  en_HK 
dc.identifier.epage  70  en_HK 
dc.publisher.place  Germany   
dc.identifier.scopusauthorid  Chan, JWT=16021445200   
dc.identifier.scopusauthorid  Chin, FYL=7005101915   
dc.identifier.scopusauthorid  Ye, D=16023572800   
dc.identifier.scopusauthorid  Zhang, Y=7601329213   
dc.identifier.scopusauthorid  Zhu, H=7404663553   
dc.customcontrol.immutable  sml 151113  merged   