File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/1248377.1248418
- Scopus: eid_2-s2.0-35248877115
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Online frequency allocation in cellular networks
Title | Online frequency allocation in cellular networks |
---|---|
Authors | |
Keywords | Cellular networks Competitive analysis Frequency allocation On-line algorithms |
Issue Date | 2007 |
Citation | Annual Acm Symposium On Parallelism In Algorithms And Architectures, 2007, p. 241-249 How to Cite? |
Abstract | Given a mobile telephone network, whose geographical coverage area is divided into 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 and the calls will not terminate, the problem is to minimize the span of frequencies used. By first considering X-colorable networks, which is a generalization of (the 3-colorable) cellular networks, we present a (X + 1)/2-competitive online algorithm. This algorithm, when applied to cellular networks, is effectively a positive solution to the open problem posed in [8]: Does a 2-competitive online algorithm exist for frequency allocation in cellular networks? We further prove a 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 ower and upper) bounds on competitive ratios noonger hold true. For cellular networks, we show new asymptotic lower and upper bounds of 1.5 and 1.9126, respectively, which breaks through the optimal bound of 2 shown previously. Copyright 2007 ACM. |
Persistent Identifier | http://hdl.handle.net/10722/93394 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, JWT | en_HK |
dc.contributor.author | Chin, FYL | en_HK |
dc.contributor.author | Ye, D | en_HK |
dc.contributor.author | Zhang, Y | en_HK |
dc.date.accessioned | 2010-09-25T14:59:45Z | - |
dc.date.available | 2010-09-25T14:59:45Z | - |
dc.date.issued | 2007 | en_HK |
dc.identifier.citation | Annual Acm Symposium On Parallelism In Algorithms And Architectures, 2007, p. 241-249 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/93394 | - |
dc.description.abstract | Given a mobile telephone network, whose geographical coverage area is divided into 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 and the calls will not terminate, the problem is to minimize the span of frequencies used. By first considering X-colorable networks, which is a generalization of (the 3-colorable) cellular networks, we present a (X + 1)/2-competitive online algorithm. This algorithm, when applied to cellular networks, is effectively a positive solution to the open problem posed in [8]: Does a 2-competitive online algorithm exist for frequency allocation in cellular networks? We further prove a 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 ower and upper) bounds on competitive ratios noonger hold true. For cellular networks, we show new asymptotic lower and upper bounds of 1.5 and 1.9126, respectively, which breaks through the optimal bound of 2 shown previously. Copyright 2007 ACM. | en_HK |
dc.language | eng | en_HK |
dc.relation.ispartof | Annual ACM Symposium on Parallelism in Algorithms and Architectures | en_HK |
dc.subject | Cellular networks | en_HK |
dc.subject | Competitive analysis | en_HK |
dc.subject | Frequency allocation | en_HK |
dc.subject | On-line algorithms | en_HK |
dc.title | Online frequency allocation in cellular networks | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Chin, FYL:chin@cs.hku.hk | en_HK |
dc.identifier.authority | Chin, FYL=rp00105 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1145/1248377.1248418 | en_HK |
dc.identifier.scopus | eid_2-s2.0-35248877115 | en_HK |
dc.identifier.hkuros | 128859 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-35248877115&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.spage | 241 | en_HK |
dc.identifier.epage | 249 | en_HK |
dc.identifier.scopusauthorid | Chan, JWT=16021445200 | en_HK |
dc.identifier.scopusauthorid | Chin, FYL=7005101915 | en_HK |
dc.identifier.scopusauthorid | Ye, D=16023572800 | en_HK |
dc.identifier.scopusauthorid | Zhang, Y=7601329213 | en_HK |