1893Accesses
415Citations
11 Altmetric
Abstract
For any listL ofn numbers in (0, 1) letL* denote the minimum number of unit capacity bins needed to pack the elements ofL. We prove that, for every positive ε, there exists anO(n)-time algorithmS such that, ifS(L) denotes the number of bins used byS forL, thenS(L)/L*≦1+ε for anyL providedL* is sufficiently large.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Starting from 10 chapters or articles per month
- Access and download chapters and articles from more than 300k books and 2,500 journals
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, books and news in related subjects, suggested using machine learning.References
M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest andR. E. Tarjan, Time bounds for selection,J. Comput. Sys. Sci.,7 (1973), 448–461.
M. R. Garey, R. L. Graham, D. S. Johnson andA. C. Yao, Multiprocessor scheduling as generalized bin-packing,J. Combinatorial Theory A21 (1976), 257–298.
M. R. Garey andD. S. Johnson,Computers and Intractability, Freeman, San Francisco, 1979.
M. R. Garey andD. S. Johnson, Approximation algorithms for bin packing problems: a survey,preprint 1980.
D. S. Johnson,Near optimal bin packing algorithms, Ph. D. Th., MIT, Cambridge, Mass., June 1973.
D. S. Johnson, Fast algorithms for bin packing,J. Comptr. Syst. Sci.8 (1974), 272–314.
D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey andR. L. Graham, Worst case bounds for simple one-dimensional packing algorithms,SIAM J. Comptg.3 (1974), 299–325.
R. M. Karp, Reducibility among combinatorial problems, in:Complexity of Computer calculations. (R. E. Miller and J. W. Thatcher, Eds.) Plenum Press, New York, 1972, 85–103.
D. E. Knuth,The Art of Computer Programming, Vol. 3, Sorting and Searching, Addison-Wesley, Reading, Mass., 1973.
A. Schönhage, M. S. Paterson andN. Pippenger, Finding the median,J. Comput. Sys. Sci.13 (1976), 184–199.
A. C. Yao, New algorithms for bin packing.J. ACM27, 2 (Apr. 1980).
J. L. Bentley, Probabilistic analysis of algorithms,Applied Probability—Computer Science, the Interface, Boca Raton, Florida, January 1981.
P. C. Gilmore andR. E. Gomory, A linear programming approach to the cutting-stock problem,Operations Research9 (1961), 849–859.
O. H. Ibarra andC. E. Kim, Fast approximation algorithms for the knapsack and sum of subset problems,Journal of the ACM22 (1975), 463–468.
L. V. Kantorovtch, Mathematical methods of organizing and planning production,Management Science6, 4 (July 1960), 366-422.
S. Sahni, General techniques for combinatorial approximation,Operations Research25, 6 (1977), 920-936.
B. W. Weide,Statistical Methods in Algorithm Design and Analysis, Ph.D. Thesis, Carnegie-Mellon University, Pittsburgh, Pennsylvania (August 1978); appeared as CMU Computer Science Report CMU-CS-78-142.
Author information
G. S. Lueker
Present address: , 4 bis rue Wulfran Puget, 13 008, Marseille, France
Authors and Affiliations
C. N. R. S., 54 Bd. Raspail, 75 006, Paris, France
W. Fernandez de la Vega
Dept. Info. Comp. Sci., Univ. of California, 92 717, Irvine, CA, U.S.A.
G. S. Lueker
- W. Fernandez de la Vega
Search author on:PubMed Google Scholar
- G. S. Lueker
Search author on:PubMed Google Scholar
Additional information
The work of this author was supported by NSF Grant MCS 70-04997.
Rights and permissions
About this article
Cite this article
Fernandez de la Vega, W., Lueker, G.S. Bin packing can be solved within 1 + ε in linear time.Combinatorica1, 349–355 (1981). https://doi.org/10.1007/BF02579456
Received:
Issue date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative