A note on a selfish bin packing problem

Ruixin Ma (), György Dósa (), Xin Han (), Hing-Fung Ting (), Deshi Ye () and Yong Zhang ()

Journal of Global Optimization, 2013, vol. 56, issue 4, 1457-1462

Abstract: In 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.69103OPT + 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. Copyright Springer Science+Business Media, LLC. 2013

Keywords: Nash Equilibrium; Bin packing; Approximation ratio (search for similar items in EconPapers)
Date: 2013
References: View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10898-012-9856-9 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:56:y:2013:i:4:p:1457-1462

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-012-9856-9

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().