nach oben

Journal of Combinatorial Optimization

Erschienen in:

09.06.2020

Truthful mechanism design for bin packing with applications on cloud computing

verfasst von: Deshi Ye, Feng Xie, Guochuan Zhang

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2022

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we study a mechanism design for the bin packing problem, which can model a reversed auction on cloud computing. A cloud computing platform has a set of jobs and would like to rent VM instances to process these jobs from cloud providers. In the auction model, each cloud provider (agent) who owns VM instances will submit a bid on the costs for using such VM instances. The mechanism determines the number of VM instances from each agent, and payments that have to be paid for using the chosen VM instances. The utility of an agent is the payment received minus the true cost. Our proposed mechanism is a deterministic truthful mechanism that the utility of each agent is maximized by revealing the true cost. Next, we provide the analysis of the approximation ratios, and then run experiments using both realistic workload and uniformly random data to show the performance of the proposed mechanisms.

Vorheriger Artikel Due date assignment and two-agent scheduling under multitasking environment

Nächster Artikel Online economic ordering problem for deteriorating items with limited price information

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

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!

Jetzt informieren

Archer A (2004) Mechanisms for discrete optimization with rational agents. Ph.D. thesis, Cornell University

Archer A, Tardos E (2001) Truthful mechanisms for one-parameter agents. In: Proceedings of the 42nd IEEE symposium on Foundations of Computer Science. IEEE Computer Society, pp 482–491

Bansal N, Elias M, Khan A (2016) Improved approximation for vector bin packing. In: Proceedings of the 27th annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM-SIAM, pp 1561–1579

Briest P, Krysta P, Vöcking B (2011) Approximation techniques for utilitarian mechanism design. SIAM J Comput 40(6):1587–1622MathSciNetCrossRef

Chekuri C, Gamzu I (2009) Truthful mechanisms via greedy iterative packing. In: Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Springer, pp 56–69

Chekuri C, Khanna S (2004) On multidimensional packing problems. SIAM J Comput 33(4):837–851MathSciNetCrossRef

Coffman EG Jr, Csirik J, Galambos G, Martello S, Vigo D (2013) Bin packing approximation algorithms: survey and classification. In: Handbook of combinatorial optimization. Springer, pp 455–531

de La Vega WF, Lueker GS (1981) Bin packing can be solved within 1+ \(\varepsilon \) in linear time. Combinatorica 1(4):349–355MathSciNetCrossRef

Epstein L, Levin A (2008) An aptas for generalized cost variable-sized bin packing. SIAM J Comput 38(1):411–428MathSciNetCrossRef

Friesen DK, Langston MA (1986) Variable sized bin packing. SIAM J Comput 15(1):222–230CrossRef

Gabay M, Zaourar S (2015) Vector bin packing with heterogeneous bins: application to the machine reassignment problem. Ann Oper Res 242:161–194MathSciNetCrossRef

Johnson DS (2016) Vector bin packing. In: Encyclopedia of algorithms, pp 2319–2323

Kang J, Park S (2003) Algorithms for the variable sized bin packing problem. Eur J Oper Res 147(2):365–372MathSciNetCrossRef

Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, BerlinCrossRef

Mashayekhy L, Nejad MM, Grosu D (2015a) Physical machine resource management in clouds: a mechanism design approach. IEEE Trans Cloud Comput 3(3):247–260CrossRef

Mashayekhy L, Nejad MM, Grosu D (2015b) A ptas mechanism for provisioning and allocation of heterogeneous cloud resources. IEEE Trans Parallel Distrib Syst 26(9):2386–2399CrossRef

Mu’Alem A, Nisan N (2008) Truthful approximation mechanisms for restricted combinatorial auctions. Games Econ Behav 64(2):612–631MathSciNetCrossRef

Murgolo FD (1988) Anomalous behavior in bin packing algorithms. Discrete Appl Math 21(3):229–243MathSciNetCrossRef

Nejad MM, Mashayekhy L, Grosu D (2013) A family of truthful greedy mechanisms for dynamic virtual machine provisioning and allocation in clouds. In: IEEE CLOUD, pp 188–195

Nisan N, Ronen A (2007) Computationally feasible VCG mechanisms. J Artif Intell Res (JAIR) 29:19–47MathSciNetCrossRef

Nisan N, Roughgarden T, Tardos E, Vazirani VV (2007) Algorithmic game theory, vol 1. Cambridge University Press, CambridgeCrossRef

Reiss C, Wilkes J, Hellerstein JL (2011) Google cluster-usage traces: format + schema. Technical report, Google Inc., Mountain View, CA, USA, Nov 2011. Revised 2012.03.20. Posted at http://code.google.com/p/googleclusterdata/wiki/TraceVersion2

Reiss C, Katz RH, Kozuch MA (2012) Towards understanding heterogeneous clouds at scale: Google trace analysis. ISTC-CC-TR-12-101, Carnegie Mellon University

Stillwell M, Schanzenbach D, Vivien F, Casanova H (2010) Resource allocation algorithms for virtualized service hosting platforms. J Parallel Distrib Comput 70(9):962–974CrossRef

Vickrey W (1961) Counterspeculation, auctions, and competitive sealed tenders. J Finance 16(1):8–37MathSciNetCrossRef

Woeginger GJ (1997) There is no asymptotic ptas for two-dimensional vector packing. Inf Process Lett 64(6):293–297MathSciNetCrossRef

Titel: Truthful mechanism design for bin packing with applications on cloud computing
verfasst von: Deshi Ye
Feng Xie
Guochuan Zhang
Publikationsdatum: 09.06.2020
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 4/2022
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-020-00601-4

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"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2022

Parameterized algorithms and complexity for the traveling purchaser problem and its variants

Surface polygonization of 3D objects using norm similarity

On the enumeration of minimal non-pairwise compatibility graphs

A new lower bound for the eternal vertex cover number of graphs

Regularized graph cuts based discrete tomography reconstruction methods

Strong Euler well-composedness

Premium Partner