Skip to Main Content

Bin Packing

Feature Column Archive

5. References

Assmann, S. and D. Johnson, D. Kleitman, J. Leung, On a dual version of the one-dimensional bin packing problem, J. Algorithms 5 (1984) 502-525.

Baker, B., A new proof for the first-fit decreasing bin-packing algorithm, J. Algorithms 6 (1985) 49-70.

Baker, B. and E. Coffman, Jr., A tight asymptotic bound for next-fit-decreasing bin packing, SIAM J. Alg. Disc. Math., 2 (1981) 147-152.

Bentley, J. and D. Johnson, F. Leighton, C. McGeoch, L. McGeoch, Some unexpected expected behavior results for bin packing., in Proceedings of the 16th Annual ACM Sym. on Theory of Computing, 1984, p. 279-288.

Brucker, P., Scheduling Algorithms, Springer-Verlag, New York, 1995.

Coffman, Jr., E., (Ed.), Computer & Job/Shop Scheduling Theory, Wiley, New York, 1976.

Coffman, Jr., E. An introduction to proof techniques for packing and sequencing algorithms, in Deterministic and Stochastic Scheduling, M. Dempster, et al., (eds.), Reidel, Amsterdam, 1982, p. 245-270.

Coffman, Jr., E. and C. Courcoubetis, M. Garey, D. Johnson, L. McGeoch, P. Shor, R. Weber, M. Yannakakis, Fundamental discrepancies between average-case analyses under discrete and continuous distributions: A bin packing case study, STOC, 19991, p. 230-240.

Coffman, Jr., and G. Galambos, S. Martello, and D. Vigo, Bin Packing Appoximation Algorithms: Combinatorial Analysis, in Handbook of Combinatorial Optimization, D. Du and P. Pardalos, (eds.), Kluwer, Amsterdam, 1998.

Coffman, Jr., and M. Garey, D. Johnson, Dynamic bin packing, SIAM J. Comput., 12 (1983) 227-258.

Coffman, Jr., and M. Garey, D. Johnson, Approximation Algorithms for Bin-Packing,: An updated survey, in Algorithm Design for Computer Systems Design, G. Ausiello, M. Lucertini, and P. Serafini, (eds.), Springer-Verlag, New York, 1984, 49-106.

Coffman, Jr., E. and M. Garey, D. Johnson, An application of bin-packing to multiprocessor scheduling, SIAM J. Comput., 7 (1987) 1-17.

Coffman, Jr., and M. Garey, D. Johnson, Approximation Algorithms for NP-Hard Problems, in D. Hochbaum, (ed.), Prindle Weber and Schmidt, Boston, 1996, p. 46-93.

Coffman, Jr., and M. Garey, D. Johnson, Bin Packing with divisible item sizes, J. Complexity, 3 (1987) 405-428.

Coffman, Jr., E. and G. Lueker, Probabilistic Analysis of Packing and Partition Algorithms, Wiley, New York, 1991.

Coffman, Jr., E. and G. Lueker, Approximation Algorithms for extensible bin packing, Proceedings, 12th Annual ACM-SIAM Symposium on Discrete Algorithms, 2001.

Coffman, Jr., E. and K. So, M. Hofri, A. Yao, A stochastic model of bin packing, Information and Control 44 (1980) 105-115.

Conway, R. and W. Maxwell, L. Miller, Theory of Scheduling, Addison-Wesley, Reading, 1967.

Courcoubetis, C. and R. Weber, Necessary and sufficient conditions for the stability of a bin packing system, J. Appl. Prob., 23 (1986) 989-999.

Csirik, J., The parametric behavior of the first-fit decreasing bin packing algorithm, J. Algorithms 15 (1993) 1-28.

Csirik, J. and J. Frenk, G. Galambos, A. Rinnooy Kan, Probabilistic analysis of algorithms for dual bin packing problems, J. Algorithms 12 (1991) 189-203.

Csirik, J. and D. Johnson, Bounded space on-line bin packing; best is better than first, In Proceedings, Second Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 1991, p. 309-319.

Fernandez del la Vega, W. and G. Lueker, Bin packing can be solved in 1 + ε in linear time, Combinatorica 1 (1981) 34-355.

Flexzar, k. and K. Hindi, New heuristics for one-dimensional bin packing, Computers and Operations Research 29 (1902) 821-839.

Floyd, S. and R. Karp, FFD bin packing for item sizes with distribution on [0, 1/2], Algorithmica, 6 (1991) 222-240.

French, S., Sequencing and Scheduling, Wiley, New York, 1982.

Garey, M. and R. Graham, D. Johnson, A. Yao, Resource constrained scheduling as generalized bin packing, J. Combinatorial Theory Ser. A, 21 (1976) 257-298.

Garey, M., and D. Johnson, Approximation algorithms for bin packing problems-A survey, in Analysis and Design of Algorithms in Combinatorial Optimization, G. Ausiello and M. Lucertini, (eds.)., Springer-Verlag, New York, 1981, p. 147-172.

Garey, M. and D. Johnson, A 71/60 theorem for bin packing, J. of Complexity, 1 (1985) 65-106.

Graham, R., Bounds for certain multiprocessing anomalies, Bell System Tech. J., 45 (1966) 1563-1581.

Graham, R., Bounds on multiprocessing anomalies, SIAM J. Applied Math., 17 (1969) 263-269.

Graham, R., Combinatorial Scheduling, in Mathematics Today, L. Steen, (Ed.), Springer-Verlag, New York, 1978, p. 183-211.

Hofri, M., Probabilistic Analysis of Algorithms, Springer-Verlag, New York, 1987.

Johnson, D., Near-Optimal Bin Packing Algorithms, Doctoral Thesis, MIT, Cambridge, 1973.

Johnson, D., Fast algorithms for bin packing, J. Comput. System Sci., 8 (1974) 272-314.

Johnson, D. and A Demers, J. Ullman, M. Garey, R. Graham, Worst-case performance bounds for simple one-dimensional packing algorithms, SIAM J. Comput., 3 (1974) 299-325.

Karmarkar, N. and R. Karp, An efficient approximation scheme for the one-dimensional bin packing problem, Proc. 23rd Annual Symposium Foundation Computer Science (FOCS 1982), p. 312-320.

Katona, G., Edge disjoint polyp packing, Discrete Applied Mathematics 78 (1997) 133-152.

Kucera, L., Combinatorial Algorithms, Adam Hilger, Bristol, 1990.

Parker, R., Deterministic Scheduling, Chapman-Hall, 1995.

Shor, P., The average case analysis of some on-line algorithms for bin packing, Combinatorica 6 (1986) 179-200.

Shor, P., How to pack better than best-fit: Tight bounds for average-case on-line bin packing. In Proceedings, 32 Annual Symp. on Foundations of Computer Science, New York, 1991, 752-759.

Simchi-Levi, D., New worst-case results for the bin packing problem, Naval Res. Log., 4 (1994( 579-585.

Xu, K., A Bin-Packing Problem with Item Sizes in the Interval (o, a] for a ≤ 1/2, Doctoral Thesis, Chinese Academy of Sciences, Beijing, China, 1993.

Yao, A., New algorithms for bin packing. J. Assoc. Comput. Mach., 22 (1980) 207-227.

Yue, M. A simple proof of the inequality FFD(L) ≤ (11/9)OPT(L) + 1, for all L, for the FFD bin-packing algorithm, Acta. Math. Appl. Sinica 7 (1991) 321-331.

Yue, M., On the exact upper bound for the multifit processor scheduling algorithm, Ann. Oper. Res., 24 (1990) 233-260.

Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials. Some of the items above can be accessed via the ACM Portal, which also provides bibliographic services.

  1. Introduction
  2. Basic ideas
  3. More approaches to bin packing
  4. Applications of bin packing
  5. References