File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: 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 Date2005
PublisherSpringer 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. 564-573 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.7r, for any r > 1. © Springer-Verlag Berlin Heidelberg 2005.
Persistent Identifierhttp://hdl.handle.net/10722/93264
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorChan, WTen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorYe, Den_HK
dc.contributor.authorZhang, Gen_HK
dc.contributor.authorZhang, Yen_HK
dc.date.accessioned2010-09-25T14:55:51Z-
dc.date.available2010-09-25T14:55:51Z-
dc.date.issued2005en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2005, v. 3828 LNCS, p. 564-573en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93264-
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.7r, for any r > 1. © Springer-Verlag Berlin Heidelberg 2005.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.subjectBin packingen_HK
dc.subjectChannel assignmenten_HK
dc.subjectOn-line algorithmen_HK
dc.titleOnline bin packing of fragile objects with application in cellular networksen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/11600930_56en_HK
dc.identifier.scopuseid_2-s2.0-33744939706en_HK
dc.identifier.hkuros112531en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33744939706&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume3828 LNCSen_HK
dc.identifier.spage564en_HK
dc.identifier.epage573en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridChan, WT=7403918060en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridYe, D=16023572800en_HK
dc.identifier.scopusauthoridZhang, G=7405271610en_HK
dc.identifier.scopusauthoridZhang, Y=7601329213en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats