File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A note on a selfish bin packing problem

TitleA note on a selfish bin packing problem
Authors
KeywordsApproximation Ratio
Bin Packing
Nash Equilibrium
Issue Date2013
PublisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=0925-5001
Citation
Journal Of Global Optimization, 2013, v. 56 n. 4, p. 1457-1462 How to Cite?
AbstractIn this paper, we consider a selfish bin packing problem, where each item is a selfish player and wants to minimize its cost. In our new model, if there are k items packed in the same bin, then each item pays a cost 1/k, where k ≥ 1. First we find a Nash Equilibrium (NE) in time O(n log n) within a social cost at most 1.69103 OPT + 3, where OPT is the social cost of an optimal packing; where n is the number of items or players; then we give tight bounds for the worst NE on the social cost; finally we show that any feasible packing can be converged to a Nash Equilibrium in O(n 2) steps without increasing the social cost. © 2012 Springer Science+Business Media, LLC.
Persistent Identifierhttp://hdl.handle.net/10722/152492
ISSN
2015 Impact Factor: 1.219
2015 SCImago Journal Rankings: 0.992
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorMa, Ren_US
dc.contributor.authorDósa, Gen_US
dc.contributor.authorHan, Xen_US
dc.contributor.authorTing, HFen_US
dc.contributor.authorYe, Den_US
dc.contributor.authorZhang, Yen_US
dc.date.accessioned2012-06-26T06:39:38Z-
dc.date.available2012-06-26T06:39:38Z-
dc.date.issued2013en_US
dc.identifier.citationJournal Of Global Optimization, 2013, v. 56 n. 4, p. 1457-1462en_US
dc.identifier.issn0925-5001en_US
dc.identifier.urihttp://hdl.handle.net/10722/152492-
dc.description.abstractIn this paper, we consider a selfish bin packing problem, where each item is a selfish player and wants to minimize its cost. In our new model, if there are k items packed in the same bin, then each item pays a cost 1/k, where k ≥ 1. First we find a Nash Equilibrium (NE) in time O(n log n) within a social cost at most 1.69103 OPT + 3, where OPT is the social cost of an optimal packing; where n is the number of items or players; then we give tight bounds for the worst NE on the social cost; finally we show that any feasible packing can be converged to a Nash Equilibrium in O(n 2) steps without increasing the social cost. © 2012 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=0925-5001en_US
dc.relation.ispartofJournal of Global Optimizationen_US
dc.subjectApproximation Ratioen_US
dc.subjectBin Packingen_US
dc.subjectNash Equilibriumen_US
dc.titleA note on a selfish bin packing problemen_US
dc.typeArticleen_US
dc.identifier.emailTing, HF:hfting@cs.hku.hken_US
dc.identifier.authorityTing, HF=rp00177en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/s10898-012-9856-9en_US
dc.identifier.scopuseid_2-s2.0-84880819220en_US
dc.identifier.hkuros223792-
dc.identifier.spage1457en_US
dc.identifier.epage1462en_US
dc.identifier.isiWOS:000321921500013-
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridMa, R=15046740000en_US
dc.identifier.scopusauthoridDósa, G=8925424600en_US
dc.identifier.scopusauthoridHan, X=34872071800en_US
dc.identifier.scopusauthoridTing, HF=7005654198en_US
dc.identifier.scopusauthoridYe, D=16023572800en_US
dc.identifier.scopusauthoridZhang, Y=54934112300en_US
dc.identifier.citeulike10319010-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats