×

Bin packing can be solved within 1+epsilon in linear time. (English) Zbl 0485.68057


MSC:

68R99 Discrete mathematics in relation to computer science
68Q25 Analysis of algorithms and problem complexity
05B40 Combinatorial aspects of packing and covering
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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. · Zbl 0278.68033 · doi:10.1016/S0022-0000(73)80033-9
[2] 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. · Zbl 0384.90053 · doi:10.1016/0097-3165(76)90001-7
[3] M. R. Garey andD. S. Johnson,Computers and Intractability, Freeman, San Francisco, 1979. · Zbl 0411.68039
[4] M. R. Garey andD. S. Johnson, Approximation algorithms for bin packing problems: a survey,preprint 1980.
[5] D. S. Johnson,Near optimal bin packing algorithms, Ph. D. Th., MIT, Cambridge, Mass., June 1973.
[6] D. S. Johnson, Fast algorithms for bin packing,J. Comptr. Syst. Sci. 8 (1974), 272–314. · Zbl 0284.68023 · doi:10.1016/S0022-0000(74)80026-7
[7] 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. · Zbl 0297.68028 · doi:10.1137/0203025
[8] 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.
[9] D. E. Knuth,The Art of Computer Programming, Vol. 3, Sorting and Searching, Addison-Wesley, Reading, Mass., 1973. · Zbl 0191.17903
[10] A. Schönhage, M. S. Paterson andN. Pippenger, Finding the median,J. Comput. Sys. Sci. 13 (1976), 184–199. · Zbl 0335.68033 · doi:10.1016/S0022-0000(76)80029-3
[11] A. C. Yao, New algorithms for bin packing.J. ACM 27, 2 (Apr. 1980). · Zbl 0434.68053 · doi:10.1145/322186.322187
[12] J. L. Bentley, Probabilistic analysis of algorithms,Applied Probability–Computer Science, the Interface, Boca Raton, Florida, January 1981.
[13] P. C. Gilmore andR. E. Gomory, A linear programming approach to the cutting-stock problem,Operations Research 9 (1961), 849–859. · Zbl 0096.35501 · doi:10.1287/opre.9.6.849
[14] O. H. Ibarra andC. E. Kim, Fast approximation algorithms for the knapsack and sum of subset problems,Journal of the ACM 22 (1975), 463–468. · Zbl 0345.90049 · doi:10.1145/321906.321909
[15] L. V. Kantorovtch, Mathematical methods of organizing and planning production,Management Science 6, 4 (July 1960), 366-422. · Zbl 0995.90532 · doi:10.1287/mnsc.6.4.366
[16] S. Sahni, General techniques for combinatorial approximation,Operations Research 25, 6 (1977), 920-936. · Zbl 0386.90048 · doi:10.1287/opre.25.6.920
[17] 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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.