Bin Packing
5. References
Assmann, S. and D. Johnson, D. Kleitman, J. Leung, On a dual version of the onedimensional bin packing problem, J. Algorithms 5 (1984) 502525.
Baker, B., A new proof for the firstfit decreasing binpacking algorithm, J. Algorithms 6 (1985) 4970.
Baker, B. and E. Coffman, Jr., A tight asymptotic bound for nextfitdecreasing bin packing, SIAM J. Alg. Disc. Math., 2 (1981) 147152.
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. 279288.
Brucker, P., Scheduling Algorithms, SpringerVerlag, 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. 245270.
Coffman, Jr., E. and C. Courcoubetis, M. Garey, D. Johnson, L. McGeoch, P. Shor, R. Weber, M. Yannakakis, Fundamental discrepancies between averagecase analyses under discrete and continuous distributions: A bin packing case study, STOC, 19991, p. 230240.
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) 227258.
Coffman, Jr., and M. Garey, D. Johnson, Approximation Algorithms for BinPacking,: An updated survey, in Algorithm Design for Computer Systems Design, G. Ausiello, M. Lucertini, and P. Serafini, (eds.), SpringerVerlag, New York, 1984, 49106.
Coffman, Jr., E. and M. Garey, D. Johnson, An application of binpacking to multiprocessor scheduling, SIAM J. Comput., 7 (1987) 117.
Coffman, Jr., and M. Garey, D. Johnson, Approximation Algorithms for NPHard Problems, in D. Hochbaum, (ed.), Prindle Weber and Schmidt, Boston, 1996, p. 4693.
Coffman, Jr., and M. Garey, D. Johnson, Bin Packing with divisible item sizes, J. Complexity, 3 (1987) 405428.
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 ACMSIAM 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) 105115.
Conway, R. and W. Maxwell, L. Miller, Theory of Scheduling, AddisonWesley, Reading, 1967.
Courcoubetis, C. and R. Weber, Necessary and sufficient conditions for the stability of a bin packing system, J. Appl. Prob., 23 (1986) 989999.
Csirik, J., The parametric behavior of the firstfit decreasing bin packing algorithm, J. Algorithms 15 (1993) 128.
Csirik, J. and J. Frenk, G. Galambos, A. Rinnooy Kan, Probabilistic analysis of algorithms for dual bin packing problems, J. Algorithms 12 (1991) 189203.
Csirik, J. and D. Johnson, Bounded space online bin packing; best is better than first, In Proceedings, Second Annual ACMSIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 1991, p. 309319.
Fernandez del la Vega, W. and G. Lueker, Bin packing can be solved in 1 + ε in linear time, Combinatorica 1 (1981) 34355.
Flexzar, k. and K. Hindi, New heuristics for onedimensional bin packing, Computers and Operations Research 29 (1902) 821839.
Floyd, S. and R. Karp, FFD bin packing for item sizes with distribution on [0, 1/2], Algorithmica, 6 (1991) 222240.
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) 257298.
Garey, M., and D. Johnson, Approximation algorithms for bin packing problemsA survey, in Analysis and Design of Algorithms in Combinatorial Optimization, G. Ausiello and M. Lucertini, (eds.)., SpringerVerlag, New York, 1981, p. 147172.
Garey, M. and D. Johnson, A 71/60 theorem for bin packing, J. of Complexity, 1 (1985) 65106.
Graham, R., Bounds for certain multiprocessing anomalies, Bell System Tech. J., 45 (1966) 15631581.
Graham, R., Bounds on multiprocessing anomalies, SIAM J. Applied Math., 17 (1969) 263269.
Graham, R., Combinatorial Scheduling, in Mathematics Today, L. Steen, (Ed.), SpringerVerlag, New York, 1978, p. 183211.
Hofri, M., Probabilistic Analysis of Algorithms, SpringerVerlag, New York, 1987.
Johnson, D., NearOptimal Bin Packing Algorithms, Doctoral Thesis, MIT, Cambridge, 1973.
Johnson, D., Fast algorithms for bin packing, J. Comput. System Sci., 8 (1974) 272314.
Johnson, D. and A Demers, J. Ullman, M. Garey, R. Graham, Worstcase performance bounds for simple onedimensional packing algorithms, SIAM J. Comput., 3 (1974) 299325.
Karmarkar, N. and R. Karp, An efficient approximation scheme for the onedimensional bin packing problem, Proc. 23rd Annual Symposium Foundation Computer Science (FOCS 1982), p. 312320.
Katona, G., Edge disjoint polyp packing, Discrete Applied Mathematics 78 (1997) 133152.
Kucera, L., Combinatorial Algorithms, Adam Hilger, Bristol, 1990.
Parker, R., Deterministic Scheduling, ChapmanHall, 1995.
Shor, P., The average case analysis of some online algorithms for bin packing, Combinatorica 6 (1986) 179200.
Shor, P., How to pack better than bestfit: Tight bounds for averagecase online bin packing. In Proceedings, 32 Annual Symp. on Foundations of Computer Science, New York, 1991, 752759.
SimchiLevi, D., New worstcase results for the bin packing problem, Naval Res. Log., 4 (1994( 579585.
Xu, K., A BinPacking 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) 207227.
Yue, M. A simple proof of the inequality FFD(L) ≤ (11/9)OPT(L) + 1, for all L, for the FFD binpacking algorithm, Acta. Math. Appl. Sinica 7 (1991) 321331.
Yue, M., On the exact upper bound for the multifit processor scheduling algorithm, Ann. Oper. Res., 24 (1990) 233260.
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.

Introduction

Basic ideas

More approaches to bin packing

Applications of bin packing

References