File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Online bin packing of fragile objects with application in cellular networks

TitleOnline bin packing of fragile objects with application in cellular networks
Authors
KeywordsBin Packing
Channel Assignment
On-Line Algorithm
Issue Date2007
PublisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905
Citation
Journal Of Combinatorial Optimization, 2007, v. 14 n. 4, p. 427-435 How to Cite?
AbstractWe 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 on-line 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/4+3r/2, for any r>1. © 2007 Springer Science+Business Media, LLC.
Persistent Identifierhttp://hdl.handle.net/10722/152363
ISSN
2015 Impact Factor: 1.08
2015 SCImago Journal Rankings: 1.093
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChan, WTen_US
dc.contributor.authorChin, FYLen_US
dc.contributor.authorYe, Den_US
dc.contributor.authorZhang, Gen_US
dc.contributor.authorZhang, Yen_US
dc.date.accessioned2012-06-26T06:37:38Z-
dc.date.available2012-06-26T06:37:38Z-
dc.date.issued2007en_US
dc.identifier.citationJournal Of Combinatorial Optimization, 2007, v. 14 n. 4, p. 427-435en_US
dc.identifier.issn1382-6905en_US
dc.identifier.urihttp://hdl.handle.net/10722/152363-
dc.description.abstractWe 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 on-line 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/4+3r/2, for any r>1. © 2007 Springer Science+Business Media, LLC.en_US
dc.languageengen_US
dc.publisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905en_US
dc.relation.ispartofJournal of Combinatorial Optimizationen_US
dc.subjectBin Packingen_US
dc.subjectChannel Assignmenten_US
dc.subjectOn-Line Algorithmen_US
dc.titleOnline bin packing of fragile objects with application in cellular networksen_US
dc.typeArticleen_US
dc.identifier.emailChin, FYL:chin@cs.hku.hken_US
dc.identifier.authorityChin, FYL=rp00105en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/s10878-007-9043-yen_US
dc.identifier.scopuseid_2-s2.0-34948898024en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-34948898024&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume14en_US
dc.identifier.issue4en_US
dc.identifier.spage427en_US
dc.identifier.epage435en_US
dc.identifier.isiWOS:000249792000003-
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridChan, WT=7403918060en_US
dc.identifier.scopusauthoridChin, FYL=7005101915en_US
dc.identifier.scopusauthoridYe, D=16023572800en_US
dc.identifier.scopusauthoridZhang, G=7405271610en_US
dc.identifier.scopusauthoridZhang, Y=7601329213en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats