nach oben

Erschienen in:

2014 | OriginalPaper | Buchkapitel

An Asymptotic Competitive Scheme for Online Bin Packing

verfasst von : Lin Chen, Deshi Ye, Guochuan Zhang

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We study the online bin packing problem, in which a list of items with integral size between 1 to \(B\) arrives one at a time. Each item must be assigned in a bin of capacity \(B\) upon its arrival without any information on the next items, and the goal is to minimize the number of used bins. We present an asymptotic competitive scheme, i.e., for any \(\epsilon >0\), the asymptotic competitive ratio is at most \(\rho ^*+\epsilon \), where \(\rho ^*\) is the smallest possible asymptotic competitive ratio among all online algorithms.

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 "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

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

Vorheriges Kapitel An Exact Algorithm for Non-preemptive Peak Demand Job Scheduling

Nächstes Kapitel Randomized Online Algorithms for Set Cover Leasing Problems

Balogh, J., Békési, J., Galambos, G.: New lower bounds for certain classes of bin packing algorithms. In: Jansen, K., Solis-Oba, R. (eds.) WAOA 2010. LNCS, vol. 6534, pp. 25–36. Springer, Heidelberg (2011)CrossRef

Boyar, J., Epstein, L., Favrholdt, L.M., et al.: The maximum resource bin packing problem. Theoret. Comput. Sci. 362, 127–139 (2006)CrossRefMATHMathSciNet

Brown, D., Baker, B.S., Katseff, H.P.: Lower bounds for on-line two-dimensional packing algorithms. Acta Informatica 18, 207–225 (1982)CrossRefMATHMathSciNet

Chen, L., Ye, D., Zhang, G.: Approximating the optimal competitive ratio for an ancient online scheduling problem. CoRR, abs/1302.3946v1 (2013)

Dośa, G., Sgall, J.: First fit bin packing: A tight analysis. In: Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 538–549 (2013)

Fernandez de La Vega, W., Lueker, G.S.: Bin packing can be solved within 1+ \(\varepsilon \) in linear time. Combinatorica 1, 349–355 (1981)CrossRefMATHMathSciNet

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the theory of of NP-Completeness. Freeman and Company, San Francisco (1979)MATH

Günther, E., Maurer, O., Megow, N., Wiese, A.: A new approach to online scheduling: Approximating the optimal competitive ratio. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 118–128 (2013)

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

10.

Johnson, D.S.: Fast algorithms for bin packing. J. Comput. Syst. Sci. 8, 272–314 (1974)CrossRefMATH

11.

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

12.

Lee, C.C., Lee, D.T.: A simple online bin packing algorithm. J. ACM 32, 562–572 (1985)CrossRefMATH

13.

Ramanan, P., Brown, D., Lee, C.C., Lee, D.T.: Online bin packing in linear time. J. Algorithms 10, 305–326 (1989)CrossRefMATHMathSciNet

14.

Seiden, S.: On the online bin packing problem. J. ACM 49, 640–671 (2002)CrossRefMathSciNet

15.

Ullman, J.: The performance of a memory allocation algorithm. Technical report. Princeton University. Dept. of Electrical Engineering (1971)

16.

Yao, A.C.C.: New algorithms for bin packing. J. ACM 27, 207–227 (1980)CrossRefMATH

17.

Y. Zhang, F.Y.L. Chin, H.-F. Ting et al. Online algorithms for 1-space bounded 2-dimensional bin packing and square packing. Theortical Comput. Sci. (2014) (to appear)

Titel: An Asymptotic Competitive Scheme for Online Bin Packing
verfasst von: Lin Chen
Deshi Ye
Guochuan Zhang
Verlag: Springer International Publishing
Buch: Combinatorial Optimization and Applications
Print ISBN: 978-3-319-12690-6

Electronic ISBN: 978-3-319-12691-3

Copyright-Jahr: 2014
DOI: https://doi.org/10.1007/978-3-319-12691-3_2

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 "Technik"

Springer Professional "Wirtschaft"

Premium Partner