Skip to main content
Log in

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

References

  1. Baker B.S., Coffman E.G.: Next-fit packs a list and its reverse into the same number of bins. SIAM J. Algebra. Discret. Methods 2(2), 147–152 (1981)

    Article  Google Scholar 

  2. Bilò, V.: On the packing of selfish items. In: The 20th IEEE International Parallel and Distributed Processing Symposium (2006)

  3. Coffman E.G., Csirik J., Woeginger G.: Bin packing theory. In: Pardalos, P., Resende, M. (eds) Handbook of Applied Optimization, Oxford University Press, New York (2002)

    Google Scholar 

  4. Coffman E.G., Galambos G., Martello S., Vigo D.: Bin packing appoximation algorithms: combinatorial analysis. In: Du, D., Pardalos, P. (eds) Handbook of Combinatorial Optimization, Kluwer, Amsterdam (1998)

    Google Scholar 

  5. Coffman E.G., Garey M.R., Johnson D.S.: Approximation Algorithms for NP-Hard Problems. PWS Publishing Co., Boston (1997)

    Google Scholar 

  6. Epstein L., Kleiman E.: Selfish bin packing. Algorithmica 60(2), 368–394 (2011)

    Article  Google Scholar 

  7. Epstein, L., Kleiman, E., Mestre, J.: Parametric packing of selfish items and the subset sum algorithm. In: The Fifth Workshop on Internet and Network Economics, pp. 67–78 (2009)

  8. Fisher D.C.: Next-fit packs a list and its reverse into the same number of bins. Oper. Res. Lett. 7(6), 291–293 (1988)

    Article  Google Scholar 

  9. Garey M.R., Graham R.L., Johnson D.S.: Resource constrained scheduling as generalized bin packing. J. Comb. Theory Ser. A 21(3), 257–298 (1976)

    Article  Google Scholar 

  10. Garey, M.R., Graham, R.L., Ullman, J.D.: Worst-case analysis of memory allocation algorithms. In: The 4th ACM Symposium on Theory of Computing, pp. 143–150 (1972)

  11. Johnson D.S., Demers A.J., Ullman J.D., Garey M.R., Graham R.L.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3(4), 299–325 (1974)

    Article  Google Scholar 

  12. Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: The 23st Annual IEEE Symposium on Foundations of Computer Science, pp. 312–320 (1982)

  13. Koutsoupias, E., Papadimitriou, C.H.: Worst-case equilibria. In: The Symposium on Theoretical Aspects of Computer Science, pp. 404–413 (1999)

  14. Mavronicolas, M., Spirakis, P.G.: The price of selfish routing. In: The 33th ACM Symposium on Theory of Computing, pp. 510–519 (2001)

  15. Onn, S.: Convex discrete optimization. In: Encyclopedia of Optimization, pp. 513–550 (2009)

  16. Roughgarden T.: Selfish Routing and the Price of Anarchy. MIT Press, Cambridge (2005)

    Google Scholar 

  17. Roughgarden, T., Tardos, É.: How bad is selfish routing? In: The 41st Annual IEEE Symposium on Foundations of Computer Science, pp. 93–102 (2000)

  18. Yu, G., Zhang, G.: Bin packing of selfish items. In: The 14th Workshop on Internet and Network Economics, pp. 446–453 (2008)

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Xin Han.

Additional information

Partially supported by “the Fundamental Research Funds for the Central Universities” and NSFC (11101065, 11171086, 11071215), No. CXB201005250021A and HK RGC grant HKU-7171/08E.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ma, R., Dósa, G., Han, X. et al. A note on a selfish bin packing problem. J Glob Optim 56, 1457–1462 (2013). https://doi.org/10.1007/s10898-012-9856-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-012-9856-9

Keywords

Navigation