Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
An Exact Algorithm for Non-preemptive Peak Demand Job Scheduling Read chapter Read first chapter

2014 | OriginalPaper | Chapter

An Asymptotic Competitive Scheme for Online Bin Packing

Authors : Lin Chen, Deshi Ye, Guochuan Zhang

Published in: Combinatorial Optimization and Applications

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter An Exact Algorithm for Non-preemptive Peak Demand Job Scheduling
next chapter Randomized Online Algorithms for Set Cover Leasing Problems
Literature
1.
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
2.
Boyar, J., Epstein, L., Favrholdt, L.M., et al.: The maximum resource bin packing problem. Theoret. Comput. Sci. 362, 127–139 (2006)CrossRefMATHMathSciNet
3.
Brown, D., Baker, B.S., Katseff, H.P.: Lower bounds for on-line two-dimensional packing algorithms. Acta Informatica 18, 207–225 (1982)CrossRefMATHMathSciNet
4.
Chen, L., Ye, D., Zhang, G.: Approximating the optimal competitive ratio for an ancient online scheduling problem. CoRR, abs/1302.3946v1 (2013)
5.
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)
6.
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
7.
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
8.
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)
9.
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.
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.
13.
14.
15.
Ullman, J.: The performance of a memory allocation algorithm. Technical report. Princeton University. Dept. of Electrical Engineering (1971)
16.
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)
Metadata
Title
An Asymptotic Competitive Scheme for Online Bin Packing
Authors
Lin Chen
Deshi Ye
Guochuan Zhang
Copyright Year
2014
Book
Combinatorial Optimization and Applications

Print ISBN: 978-3-319-12690-6

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

Copyright Year: 2014

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

Premium Partner

    Image Credits