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

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Online bin packing of fragile objects with application in cellular networks
Title  Online bin packing of fragile objects with application in cellular networks 

Authors  
Keywords  Bin packing Channel assignment Online algorithm 
Issue Date  2005 
Publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ 
Citation  Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2005, v. 3828 LNCS, p. 564573 How to Cite? 
Abstract  We study a specific bin packing problem which arises from the channel assignment problems in cellular networks. In cellular communications, frequency channels are some limited resource which may need to share by various users. However, in order to avoid signal interference among users, a user needs to specify to share the channel with at most how many other users, depending on the user's application. Under this setting, the problem of minimizing the total channels used to support all users can be modeled as a specific bin packing problem as follows: Given a set of items, each with two attributes, weight and fragility. We need to pack the items into bins such that, for each bin, the sum of weight in the bin must be at most the smallest fragility of all the items packed into the bin. The goal is to minimize the total number of bins (i.e., the channels in the cellular network) used. We consider the online version of this problem, where items arrive one by one. The next item arrives only after the current item has been packed, and the decision cannot be changed. We show that the asymptotic competitive ratio is at least 2. We also consider the case where the ratio of maximum fragility and minimum fragility is bounded by a constant. In this case, we present a class of online algorithms with asymptotic competitive ratio at most of 1.7r, for any r > 1. © SpringerVerlag Berlin Heidelberg 2005. 
Persistent Identifier  http://hdl.handle.net/10722/93264 
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, G  en_HK 
dc.contributor.author  Zhang, Y  en_HK 
dc.date.accessioned  20100925T14:55:51Z   
dc.date.available  20100925T14:55:51Z   
dc.date.issued  2005  en_HK 
dc.identifier.citation  Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2005, v. 3828 LNCS, p. 564573  en_HK 
dc.identifier.issn  03029743  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/93264   
dc.description.abstract  We study a specific bin packing problem which arises from the channel assignment problems in cellular networks. In cellular communications, frequency channels are some limited resource which may need to share by various users. However, in order to avoid signal interference among users, a user needs to specify to share the channel with at most how many other users, depending on the user's application. Under this setting, the problem of minimizing the total channels used to support all users can be modeled as a specific bin packing problem as follows: Given a set of items, each with two attributes, weight and fragility. We need to pack the items into bins such that, for each bin, the sum of weight in the bin must be at most the smallest fragility of all the items packed into the bin. The goal is to minimize the total number of bins (i.e., the channels in the cellular network) used. We consider the online version of this problem, where items arrive one by one. The next item arrives only after the current item has been packed, and the decision cannot be changed. We show that the asymptotic competitive ratio is at least 2. We also consider the case where the ratio of maximum fragility and minimum fragility is bounded by a constant. In this case, we present a class of online algorithms with asymptotic competitive ratio at most of 1.7r, for any r > 1. © SpringerVerlag Berlin Heidelberg 2005.  en_HK 
dc.language  eng  en_HK 
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/  en_HK 
dc.relation.ispartof  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  en_HK 
dc.subject  Bin packing  en_HK 
dc.subject  Channel assignment  en_HK 
dc.subject  Online algorithm  en_HK 
dc.title  Online bin packing of fragile objects with application 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.1007/11600930_56  en_HK 
dc.identifier.scopus  eid_2s2.033744939706  en_HK 
dc.identifier.hkuros  112531  en_HK 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.033744939706&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.volume  3828 LNCS  en_HK 
dc.identifier.spage  564  en_HK 
dc.identifier.epage  573  en_HK 
dc.publisher.place  Germany  en_HK 
dc.identifier.scopusauthorid  Chan, WT=7403918060  en_HK 
dc.identifier.scopusauthorid  Chin, FYL=7005101915  en_HK 
dc.identifier.scopusauthorid  Ye, D=16023572800  en_HK 
dc.identifier.scopusauthorid  Zhang, G=7405271610  en_HK 
dc.identifier.scopusauthorid  Zhang, Y=7601329213  en_HK 