Skip to main content

2017 | OriginalPaper | Buchkapitel

An Improved Mechanism for Selfish Bin Packing

verfasst von : Xin Chen, Qingqin Nong, Qizhi Fang

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Selfish bin packing can be viewed as the non-cooperative version of bin packing problem, where every item is a selfish agent and want to minimize his sharing cost with the other items packing in the same bin. In this paper, we focus on designing a new mechanism (a payoff rule) for selfish bin packing, called modified Dutch treatment mechanism. We first show that the pure Nash equilibrium exists and it can be obtained in polynomial time. We then prove that under the new mechanism, the price of anarchy (PoA) is between 1.47407 and 1.4748, improving the known results.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Bilò, V.: On the packing of selfish items. In: Proceedings of 20th IEEE International Parallel and Distributed Processing Symposium. IEEE (2006) Bilò, V.: On the packing of selfish items. In: Proceedings of 20th IEEE International Parallel and Distributed Processing Symposium. IEEE (2006)
2.
Zurück zum Zitat Coffman, J.E.G., Csirik, J.: Performance guarantees for one-dimensional bin packing. In: Handbook of Approximation Algorithms and Metaheuristics, p. 32-1 (2007) Coffman, J.E.G., Csirik, J.: Performance guarantees for one-dimensional bin packing. In: Handbook of Approximation Algorithms and Metaheuristics, p. 32-1 (2007)
3.
Zurück zum Zitat Coffman, J.E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Approximation Algorithms for NP-Hard Problems, pp. 46–93. PWS Publishing Co. (1996) Coffman, J.E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Approximation Algorithms for NP-Hard Problems, pp. 46–93. PWS Publishing Co. (1996)
5.
Zurück zum Zitat Dósa, G., Sgall, J.: First Fit bin packing: a tight analysis. LIPIcs-Leibniz International Proceedings in Informatics. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2013) Dósa, G., Sgall, J.: First Fit bin packing: a tight analysis. LIPIcs-Leibniz International Proceedings in Informatics. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2013)
7.
Zurück zum Zitat Epstein, L., Kleiman, E., Mestre, J.: Parametric packing of selfish items and the subset sum algorithm. Algorithmica 74(1), 177–207 (2016)CrossRefMATHMathSciNet Epstein, L., Kleiman, E., Mestre, J.: Parametric packing of selfish items and the subset sum algorithm. Algorithmica 74(1), 177–207 (2016)CrossRefMATHMathSciNet
8.
Zurück zum Zitat Garey, M.R., Graham, R.L., Ullman, J.D.: Worst-case analysis of memory allocation algorithms. In: Proceedings of the Fourth Annual ACM Symposium on Theory of Computing, pp. 143–150. ACM (1972) Garey, M.R., Graham, R.L., Ullman, J.D.: Worst-case analysis of memory allocation algorithms. In: Proceedings of the Fourth Annual ACM Symposium on Theory of Computing, pp. 143–150. ACM (1972)
9.
Zurück zum Zitat Johnson, D.S., Demers, A., Ullman, J.D., et al.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3(4), 299–325 (1974)CrossRefMATHMathSciNet Johnson, D.S., Demers, A., Ullman, J.D., et al.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3(4), 299–325 (1974)CrossRefMATHMathSciNet
12.
14.
Zurück zum Zitat Neumann, L.J., Morgenstern, O.: Theory of Games and Economic Behavior. Princeton University Press, Princeton (1947)MATH Neumann, L.J., Morgenstern, O.: Theory of Games and Economic Behavior. Princeton University Press, Princeton (1947)MATH
15.
Zurück zum Zitat Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)CrossRefMATH Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)CrossRefMATH
Metadaten
Titel
An Improved Mechanism for Selfish Bin Packing
verfasst von
Xin Chen
Qingqin Nong
Qizhi Fang
Copyright-Jahr
2017
DOI
https://doi.org/10.1007/978-3-319-71147-8_17