nach oben

Journal of Scheduling

Erschienen in:

04.10.2018

Quality of strong equilibria for selfish bin packing with uniform cost sharing

verfasst von: György Dósa, Leah Epstein

Erschienen in: Journal of Scheduling | Ausgabe 4/2019

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The bin packing problem deals with packing items of sizes no larger than 1 into unit capacity bins. Here, we analyze a class of bin packing games where the cost of an item is 1 over the total number of items packed into its bin, which is a bin packing congestion game. We study strong equilibria and find the tight values of the SPoA and SPoS, that is, asymptotic approximation ratios of the worst and best strong equilibria. We show that these values are approximately 1.69103 and 1.611824, respectively. In particular, we observe that the two values are not equal, showing a difference from other known kinds of cost sharing approaches.

Vorheriger Artikel The single-processor scheduling problem with time restrictions: complexity and related problems

Nächster Artikel Lower bounds for online bin covering-type problems

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!

Jetzt informieren

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!

Jetzt informieren

Andelman, N., Feldman, M., & Mansour, Y. (2009). Strong price of anarchy. Games and Economic Behavior, 65(2), 289–317.CrossRef

Anshelevich, E., Dasgupta, A., Kleinberg, J. M., Tardos, É., Wexler, T., & Roughgarden, T. (2008). The price of stability for network design with fair cost allocation. SIAM Journal on Computing, 38(4), 1602–1623.CrossRef

Aumann, R . J. (1959). Acceptable points in general cooperative n-person games. In A . W. Tucker & R . D. Luce (Eds.), Contributions to the Theory of Games IV, annals of mathematics study 40 (pp. 287–324). Princeton: Princeton University Press.

Baker, B. S., & Coffman, E. G, Jr. (1981). A tight asymptotic bound for next-fit-decreasing bin-packing. SIAM Journal on Algebraic and Discrete Methods, 2(2), 147–152.CrossRef

Bilò, V. (2006). On the packing of selfish items. In Proceedings of the 20th international parallel and distributed processing symposium (IPDPS’06). IEEE.

Caprara, A., & Pferschy, U. (2004). Worst-case analysis of the subset sum algorithm for bin packing. Operations Research Letters, 32(2), 159–166.CrossRef

Chien, S., & Sinclair, A. (2009). Strong and pareto price of anarchy in congestion games. In Proceedings of the 36th international colloquium on automata, languages and programming (ICALP’09) (pp. 279–291).

Coffman, E . G., Garey, M . R., & Johnson, D . S. (1997). Approximation algorithms for bin packing: A survey. In D. Hochbaum (Ed.), Approximation algorithms. Boston: PWS Publishing Company.

Czumaj, A., & Vöcking, B. (2007). Tight bounds for worst-case equilibria. ACM Transactions on Algorithms, 3(1).

Dósa, Gy., & Epstein, L. (2012). Generalized selfish bin packing. CoRR, abs/1202.4080.

Dósa, Gy., & Epstein, L. Selfish bin packing with general weights. Manuscript.

Dósa, Gy., & Epstein, L. The price of anarchy for selfish bin packing with uniform cost sharing. Manuscript.

Epstein, A., Feldman, M., & Mansour, Y. (2009). Strong equilibrium in cost sharing connection games. Games and Economic Behavior, 67(1), 51–68.CrossRef

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

Epstein, L., Kleiman, E., & Mestre, J. (2016). Parametric packing of selfish items and the Subset Sum algorithm. Algorithmica, 74(1), 177–207.CrossRef

Epstein, L., & Levin, A. (2008). On bin packing with conflicts. SIAM Journal on Optimization, 19(3), 1270–1298.CrossRef

Fernandes, C. G., Ferreira, C. E., Miyazawa, F. K., & Wakabayashi, Y. (2011). Selfish square packing. Electronic Notes in Discrete Mathematics, 37, 369–374.CrossRef

Fiat, A., Kaplan, H., Levy, M., & Olonetsky, S. (2007). Strong price of anarchy for machine load balancing. In Proceedings of the 34th international colloquium on automata, languages and programming (ICALP’07) (pp. 583–594).

Fisher, D. C. (1988). Next-fit packs a list and its reverse into the same number of bins. Operations Research Letters, 7(6), 291–293.CrossRef

Galambos, G., & Woeginger, G. J. (1993). Repacking helps in bounded space online bin packing. Computing, 49, 329–338.CrossRef

Graham, R. L. (1972). Bounds on multiprocessing anomalies and related packing algorithms. In Proceedings of the 1972 spring joint computer conference (pp. 205–217).

Holzman, R., & Law-Yone, N. (1997). Strong equilibrium in congestion games. Games and Economic Behavior, 21(1–2), 85–101.CrossRef

Ieong, S., McGrew, B., Nudelman, E., Shoham, Y., & Sun, Q. (2005). Fast and compact: A simple class of congestion games, In Proceedings of the 20th national conference on artificial intelligence (pp. 489–494).

Johnson, D. S., Demers, A., Ullman, J. D., Garey, M. R., & Graham, R. L. (1974). Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing, 3, 256–278.CrossRef

Koutsoupias, E., & Papadimitriou, C. H.(1999). Worst-case equilibria. In Proceedings of the 16th annual symposium on theoretical aspects of computer science (STACS’99) (pp. 404–413).

Lee, C. C., & Lee, D. T. (1985). A simple online bin packing algorithm. Journal of the ACM, 32(3), 562–572.CrossRef

Ma, R., Dósa, Gy, Han, X., Ting, H.-F., Ye, D., & Zhang, Y. (2013). A note on a selfish bin packing problem. Journal of Global Optimization, 56(4), 1457–1462.CrossRef

Mavronicolas, M., & Spirakis, P. G. (2007). The price of selfish routing. Algorithmica, 48(1), 91–126.CrossRef

Nash, J. (1951). Non-cooperative games. Annals of Mathematics, 54(2), 286–295.CrossRef

Roughgarden, T. (2005). Selfish routing and the price of anarchy. Cambridge: MIT Press.

Roughgarden, T., & Tardos, É. (2002). How bad is selfish routing? Journal of the ACM, 49(2), 236–259.CrossRef

Tennenholtz, M., & Rozenfeld, O. (2006). Strong and correlated strong equilibria in monotone congestion games. In Proceedings of the 2nd international workshop on internet and network economics (WINE’06) (pp. 74–86).

Yu, G., & Zhang, G.(2008). Bin packing of selfish items. In The 4th international workshop on internet and network economics (WINE’08) (pp. 446–453).

Titel: Quality of strong equilibria for selfish bin packing with uniform cost sharing
verfasst von: György Dósa
Leah Epstein
Publikationsdatum: 04.10.2018
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 4/2019
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-018-0587-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2019

Parallel machine makespan minimization subject to machine availability and total completion time constraints

The single-processor scheduling problem with time restrictions: complexity and related problems

Malleable scheduling for flows of jobs and applications to MapReduce

Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs

Lower bounds for online bin covering-type problems

The evolution of schematic representations of flow shop scheduling problems