File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Frequency allocation problems for linear cellular networks

TitleFrequency allocation problems for linear cellular networks
Authors
Issue Date2006
PublisherSpringer 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, 18-20 December 2006. In Lecture Notes In Computer Science, 2006, v. 4288, p. 61-70 How to Cite?
AbstractWe 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/2-competitive 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 Springer-Verlag Berlin/Heidelberg.
Persistent Identifierhttp://hdl.handle.net/10722/93145
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorChan, WTen_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-25T14:52:15Z-
dc.date.available2010-09-25T14:52:15Z-
dc.date.issued2006en_HK
dc.identifier.citationThe 17th International Symposium on Algorithms and Computation (ISAAC 2006), Kolkata, India, 18-20 December 2006. In Lecture Notes In Computer Science, 2006, v. 4288, p. 61-70en_HK
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/93145-
dc.description.abstractWe 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/2-competitive 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 Springer-Verlag Berlin/Heidelberg.-
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/-
dc.relation.ispartofLecture Notes in Computer Scienceen_HK
dc.titleFrequency allocation problems for linear cellular networksen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChin, FYL: chin@cs.hku.hken_HK
dc.identifier.emailYe, D: yedeshi@cs.hku.hken_HK
dc.identifier.emailZhang, Y: yzhang.hku@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/11940128_8-
dc.identifier.scopuseid_2-s2.0-77249095123-
dc.identifier.hkuros128855en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-77249095123&selection=ref&src=s&origin=recordpage-
dc.identifier.volume4288-
dc.identifier.spage61en_HK
dc.identifier.epage70en_HK
dc.publisher.placeGermany-
dc.identifier.scopusauthoridChan, JWT=16021445200-
dc.identifier.scopusauthoridChin, FYL=7005101915-
dc.identifier.scopusauthoridYe, D=16023572800-
dc.identifier.scopusauthoridZhang, Y=7601329213-
dc.identifier.scopusauthoridZhu, H=7404663553-
dc.customcontrol.immutablesml 151113 - merged-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats