{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,27]],"date-time":"2026-07-27T14:32:20Z","timestamp":1785162740910,"version":"3.55.0"},"publisher-location":"Boston, MA","reference-count":107,"publisher":"Springer US","isbn-type":[{"value":"9781441948137","type":"print"},{"value":"9781475730234","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/978-1-4757-3023-4_3","type":"book-chapter","created":{"date-parts":[[2013,2,21]],"date-time":"2013-02-21T08:28:50Z","timestamp":1361435330000},"page":"151-207","source":"Crossref","is-referenced-by-count":38,"title":["Bin Packing Approximation Algorithms: Combinatorial Analysis"],"prefix":"10.1007","author":[{"given":"Edward G.","family":"Coffman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gabor","family":"Galambos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Silvano","family":"Martello","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniele","family":"Vigo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"3_CR1","unstructured":"M. Adler, P. B. Gibbons, and Y. Matias. Scheduling space sharing for internet advertising. Technical report, Bell Labs, Lucent Technologies, Murray Hill, NJ 07974, 1997."},{"key":"3_CR2","first-page":"130","volume-title":"Proc. 29th Annual Acm Symp. Theory of Comput","author":"S Albers","year":"1997","unstructured":"S. Albers. Better bounds for on-line scheduling. In Proc. 29th Annual ACM Symp. Theory of Comput., pages 130\u2013139, 1997."},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1016\/0890-5401(89)90003-5","volume":"82","author":"RJ Anderson","year":"1989","unstructured":"R. J. Anderson, E. W. Mayr, and M. K. Warmuth. Parallel approximation algorithms for bin packing. Inf. and Comput., 82: 262\u2013277, 1989.","journal-title":"Inf. and Comput"},{"key":"3_CR4","unstructured":"S. F. Assmann Problems in Discrete Applied Mathematics. PhD thesis, Mathematics Department MIT, Cambridge, MA, 1983."},{"key":"3_CR5","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1016\/0196-6774(84)90004-X","volume":"5","author":"SF Assmann","year":"1984","unstructured":"S. F. Assmann, D. S. Johnson, D. J. Kleitman, and J. Y.-T. Leung. On a dual version of the one-dimensional bin packing problem. J. Algorithms, 5: 502\u2013525, 1984.","journal-title":"J. Algorithms"},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0196-6774(85)90018-5","volume":"6","author":"BS Baker","year":"1985","unstructured":"B. S. Baker. A new proof for the first-fit decreasing bin-packing algorithm. J. Algorithms, 6: 49\u201370, 1985.","journal-title":"J. Algorithms"},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1016\/0196-6774(81)90034-1","volume":"2","author":"BS Baker","year":"1981","unstructured":"B. S. Baker, D. J. Brown, and H. P. Katseff. A 5\/4 algorithm for two-dimensional packing. J. Algorithms, 2: 348\u2013368, 1981.","journal-title":"J. Algorithms"},{"issue":"2","key":"3_CR8","first-page":"147152","volume":"2","author":"B. S. Baker","year":"1981","unstructured":"B. S. Baker and E. G. Coffman, Jr. A tight asymptotic bound for nextfit-decreasing bin-packing. SIAM J. Algebraic Discr. Meth.,2(2):147152, 1981.","journal-title":"SIAM J. Algebraic Discr. Meth."},{"key":"3_CR9","first-page":"51","volume-title":"Proc. 24th Annual Acm Symp. Theory of Comput","author":"Y Bartal","year":"1992","unstructured":"Y. Bartal, A. Fiat, H. Karloff, and R. Vohra. New algorithms for an ancient scheduling problem. In Proc. 24th Annual ACM Symp. Theory of Comput., pages 51\u201358, Victoria, Canada, 1992."},{"key":"3_CR10","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0020-0190(94)00026-3","volume":"50","author":"Y Bartal","year":"1994","unstructured":"Y. Bartal, H. Karloff, and Y. Rabani. A better lower bound for on-line scheduling. Inform. Process. Lett., 50: 113\u2013116, 1994.","journal-title":"Inform. Process. Lett"},{"key":"3_CR11","volume-title":"And H. Kellerer. A 5\/4 linear time bin packing algorithm. Technical Report OR-97-2, Teachers Trainer College","author":"J B\u00e8k\u00e8si","year":"1997","unstructured":"J. B\u00e8k\u00e8si, G. Galambos, and H. Kellerer. A 5\/4 linear time bin packing algorithm. Technical Report OR-97\u20132, Teachers Trainer College, Szeged, Hungary, 1997."},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0167-6377(83)90042-1","volume":"2","author":"J Blazewicz","year":"1983","unstructured":"J. Blazewicz and K. Ecker. A linear time algorithm for restricted bin packing and scheduling problems. Oper. Res. Lett., 2: 80\u201383, 1983.","journal-title":"Oper. Res. Lett"},{"key":"3_CR13","volume-title":"A lower bound for on-line one-dimensional bin-packing algorithms. Technical Report R-864, University of Illinois","author":"DJ Brown","year":"1979","unstructured":"D. J. Brown. A lower bound for on-line one-dimensional bin-packing algorithms. Technical Report R-864, University of Illinois, Coordinated sc. lab., Urbana, 1979."},{"key":"3_CR14","first-page":"63","volume":"13","author":"RE Burkard","year":"1997","unstructured":"R. E. Burkard and G. Zhang. Bounded space on-line variable-sized bin packing. Acta Cybern., 13: 63\u201376, 1997.","journal-title":"Acta Cybern"},{"key":"3_CR15","unstructured":"L. M. A. Chan, D. Simchi-Levi, and J. Bramel. Worst-case analyses, linear programming, and the bin-packing problem. Unpublished manuscript, 1994."},{"key":"3_CR16","doi-asserted-by":"crossref","first-page":"760772","DOI":"10.1287\/opre.26.5.760","volume":"26","author":"A. K. Chandra","year":"1978","unstructured":"A. K. Chandra, D. S. Hirschler, and C. K. Wong. Bin packing with geometric constraints in computer network design. Oper. Res., 26: 760772, 1978.","journal-title":"Oper. Res"},{"key":"3_CR17","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0020-0190(92)90023-O","volume":"43","author":"B Chandra","year":"1992","unstructured":"B. Chandra. Does randomization help in on-line bin packing? Inform. Process. Lett., 43: 15\u201319, 1992.","journal-title":"Inform. Process. Lett"},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0167-6377(94)90071-X","volume":"16","author":"B Chen","year":"1994","unstructured":"B. Chen, A. van Vliet, and G.J. Woeginger. New lower and upper bounds for on-line scheduling. Oper. Res. Lett., 16: 221\u2013230, 1994.","journal-title":"Oper. Res. Lett"},{"issue":"3","key":"3_CR19","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1137\/1025074","volume":"25","author":"EG Coffman","year":"1983","unstructured":"E. G. Coffman, Jr. An introduction to combinatorial models of dynamic storage allocation. SIAM Rev., 25 (3): 311\u2013325, 1983.","journal-title":"Siam Rev"},{"key":"3_CR20","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1016\/0885-064X(87)90009-4","volume":"3","author":"E. G. Coffman","year":"1987","unstructured":"E. G. Coffman, Jr., M. Garey, and D. S. Johnson. Bin packing with divisible item sizes. J. Complexity, 3: 405\u2013428, 1987.","journal-title":"J. Complexity"},{"issue":"1","key":"3_CR21","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1137\/0207001","volume":"7","author":"E. G. Coffman","year":"1978","unstructured":"E. G. Coffman, Jr., M. R. Garey, and D. S. Johnson. An application of bin-packing to multiprocessor scheduling. SIAM J. Comput., 7 (1): 117, 1978.","journal-title":"SIAM J. Comput"},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"E. G. Coffman, Jr., M. R. Garey, and D. S. Johnson. Approximation algorithms for bin-packing: An updated survey. In G. Ausiello, M. Lucertini, and P. Serafini, editors, Algorithm Design for Computer System Design, pages 49\u2013106. Springer Verlag, Wien, 1984.","DOI":"10.1007\/978-3-7091-4338-4_3"},{"key":"3_CR23","unstructured":"E. G. Coffman, Jr., M. R. Carey, and D. S. Johnson. Approximation algorithms for bin packing. In D. S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, pages 46\u201393. PWS Publ. Company, 1997."},{"issue":"2","key":"3_CR24","first-page":"202","volume":"8","author":"EG Coffman","year":"1979","unstructured":"E. G. Coffman, Jr. and J. Y.-T. Leung. Combinatorial analysis of an efficient algorithm for processor and storage allocation. SIAM J. Comput., 8 (2): 202\u2013217, 1979.","journal-title":"J. Y.-T. Leung. Combinatorial analysis of an efficient algorithm for processor and storage allocation. Siam J. Comput"},{"key":"3_CR25","first-page":"263","volume":"9","author":"EG Coffman","year":"1978","unstructured":"E. G. Coffman, Jr., J. Y.-T. Leung, and D. W. Ting. Bin packing: Maximizing the number of pieces packed. Acta Inform., 9: 263\u2013271, 1978.","journal-title":"J. Y.-T. Leung, and D. W. Ting. Bin packing: Maximizing the number of pieces packed. Acta Inform"},{"key":"3_CR26","unstructured":"E. G. Coffman, Jr. and G. S. Lueker. Probabilistic analysis of packing and partitioning algorithms. John Wiley & Sons, New York, 1991."},{"key":"3_CR27","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1007\/BF00289157","volume":"26","author":"J Csirik","year":"1989","unstructured":"J. Csirik. An on-line algorithm for variable-sized bin packing. Acta Inform., 26: 697\u2013709, 1989.","journal-title":"Acta Inform"},{"key":"3_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.1993.1028","volume":"15","author":"J Csirik","year":"1993","unstructured":"J. Csirik. The parametric behaviour of the first fit decreasing bin-packing algorithm. J. Algorithms, 15: 1\u201328, 1993.","journal-title":"J. Algorithms"},{"key":"3_CR29","first-page":"52","volume-title":"Proc. Euro Vi Conf.","author":"J Csirik","year":"1983","unstructured":"J. Csirik, G. Galambos, and G. Turan. Some results on bin-packing. In Proc. EURO VI Conf., page 52, Vienna, Austria, 1983."},{"key":"3_CR30","first-page":"89","volume":"9","author":"J Csirik","year":"1989","unstructured":"J. Csirik and B. Imreh. On the worst-case performance of the next-k-fit bin-packing heuristic. Acta Cybern., 9: 89\u2013105, 1989.","journal-title":"Acta Cybern"},{"key":"3_CR31","unstructured":"J. Csirik and D. S. Johnson. Bounded space on-line bin-packing: best is better than first. In Proc. 2nd Annual ACM-SIAM Symp. Discr. Algorithms, pages 309\u2013319, Philadelphia, 1991."},{"key":"3_CR32","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(88)90052-2","volume":"21","author":"J Csirik","year":"1988","unstructured":"J. Csirik and V. Totik. Online algorithms for a dual version of bin paking. Discr. Appl. Math., 21: 163\u2013167, 1988.","journal-title":"Discr. Appl. Math"},{"key":"3_CR33","volume-title":"Graz (Austria)","author":"J Csirik","year":"1996","unstructured":"J. Csirik and G. J. Woeginger. Online packing and covering problems. Technical Report No. 83, T.U. Graz (Austria), 1996."},{"key":"3_CR34","unstructured":"M. Dror. Private communication."},{"key":"3_CR35","first-page":"107","volume":"9","author":"U Faigle","year":"1989","unstructured":"U. Faigle, W. Kern, and G. Turan. On the performance of on-line algorithms for particular problems. Acta Cybern., 9: 107\u2013119, 1989.","journal-title":"Acta Cybern"},{"issue":"4","key":"3_CR36","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W Fernandez","year":"1981","unstructured":"W. Fernandez de la Vega and G. S. Lueker. Bin packing can be solved within 1 + e in linear time. Combinatorica, 1 (4): 349\u2013355, 1981.","journal-title":"Combinatorica"},{"issue":"6","key":"3_CR37","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0167-6377(88)90060-0","volume":"7","author":"DC Fisher","year":"1988","unstructured":"D. C. Fisher. Next-fit packs a list and its reverse into the same number of bins. Oper. Res. Lett., 7 (6): 291\u2013293, 1988.","journal-title":"Oper. Res. Lett"},{"issue":"1","key":"3_CR38","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1137\/0213013","volume":"13","author":"DK Friesen","year":"1984","unstructured":"D. K. Friesen. Tighter bounds for the multifit processor scheduling algorithm. SIAM J. Comput., 13 (1): 170\u2013181, 1984.","journal-title":"Siam J. Comput"},{"issue":"1","key":"3_CR39","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1137\/0215016","volume":"15","author":"DK Friesen","year":"1986","unstructured":"D. K. Friesen and M. A. Langston. Variable sized bin packing. SIAM J. Comput., 15 (1): 222\u2013230, 1986.","journal-title":"Siam J. Comput"},{"issue":"1","key":"3_CR40","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1137\/0404007","volume":"4","author":"DK Friesen","year":"1991","unstructured":"D. K. Friesen and M. A. Langston. Analysis of a compound bin packing algorithm. SIAM J. Discr. Math., 4 (1): 61\u201379, 1991.","journal-title":"Siam J. Discr. Math"},{"key":"3_CR41","volume-title":"Technical Report","author":"G Galambos","year":"1985","unstructured":"G. Galambos. A new heuristic for the classical bin-packing problem. Technical Report 82, Institute fuer Mathematik, Augsburg, 1985."},{"issue":"3","key":"3_CR42","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1137\/0607041","volume":"7","author":"G Galambos","year":"1986","unstructured":"G. Galambos. Parametric lower bound for on-line bin-packing. SIAM J. Algebraic Discr. Meth., 7 (3): 362\u2013367, 1986.","journal-title":"Siam J. Algebraic Discr. Meth"},{"key":"3_CR43","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0166-218X(93)90037-O","volume":"41","author":"G Galambos","year":"1993","unstructured":"G. Galambos and J. B. G. Frenk. A simple proof of Liang\u2019s lower bound for on-line bin packing and the extension to the parametric case. Discr. Appl. Math., 41: 173\u2013178, 1993.","journal-title":"Discr. Appl. Math"},{"issue":"2","key":"3_CR44","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1137\/0222026","volume":"22","author":"G Galambos","year":"1993","unstructured":"G. Galambos and G. J. Woeginger. An on-line scheduling heuristic with better worst case ratio than graham\u2019s list scheduling. SIAM J. Comput., 22 (2): 345\u2013355, 1993.","journal-title":"Siam J. Comput"},{"key":"3_CR45","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/BF02248693","volume":"49","author":"G Galambos","year":"1993","unstructured":"G. Galambos and G. J. Woeginger. Repacking helps in bounded space on-line bin-packing. Computing, 49: 329\u2013338, 1993.","journal-title":"Computing"},{"key":"3_CR46","first-page":"25","volume":"42","author":"G Galambos","year":"1995","unstructured":"G. Galambos and G. J. Woeginger. On-line bin packing \u2014 a restricted survey. Z. Oper. Res., 42: 25\u201345, 1995.","journal-title":"Z. Oper. Res"},{"key":"3_CR47","first-page":"44","volume-title":"Algorithms and Complexity","author":"G Gambosi","year":"1990","unstructured":"G. Gambosi, A. Postiglione, and M. Talamo. New algorithms for online bin packing. In R. Petreschi, G. Ausiello, and D. P. Bovet, editors, Algorithms and Complexity, pages 44\u201359. World Scientific, Singapore, 1990."},{"key":"3_CR48","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0097-3165(76)90001-7","volume":"21","author":"M. R. Garey","year":"1976","unstructured":"M. R. Garey, R. L. Graham, D. S. Johnson, and A. C.-C. Yao. Resource constrained scheduling as generalized bin packing. J. Combin. Theory, Ser. A, 21: 257\u2013298, 1976.","journal-title":"J. Combin. Theory"},{"key":"3_CR49","volume-title":"Proc. 4th Annual ACM Symp. Theory of Comput., pages 143-150, New York","author":"MR Garey","year":"1972","unstructured":"M. R. Garey, R. L. Graham, and J. D. Ullmann. Worst-case analysis of memory allocation algorithms. In Proc. 4th Annual ACM Symp. Theory of Comput., pages 143\u2013150, New York, 1972."},{"key":"3_CR50","volume-title":"Computers and intractability (A Guide to the theory of NP-Completeness. W. H","author":"MR Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and intractability (A Guide to the theory of NP-Completeness. W. H. Freeman and Company, San Francisco, 1979."},{"key":"3_CR51","first-page":"147","volume-title":"Analysis and Design of Algorithm in Combinatorial Optimization","author":"MR Carey","year":"1981","unstructured":"M. R. Carey and D. S. Johnson. Approximation algorithm for bin-packing problems: a survey. In G. Ausiello and M. Lucertini, editors, Analysis and Design of Algorithm in Combinatorial Optimization, pages 147\u2013172. Springer Verlag, New York, 1981."},{"key":"3_CR52","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/0885-064X(85)90022-6","volume":"1","author":"MR Garey","year":"1985","unstructured":"M. R. Garey and D. S. Johnson. A 71\/60 theorem for bin packing. J. Complexity, 1: 65\u2013106, 1985.","journal-title":"J. Complexity"},{"key":"3_CR53","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1287\/opre.9.6.849","volume":"9","author":"PC Gilmore","year":"1961","unstructured":"P. C. Gilmore and R. E. Gomory. A linear programming approach to the cutting-stock problem. Oper. Res., 9: 849\u2013859, 1961.","journal-title":"Oper. Res"},{"key":"3_CR54","doi-asserted-by":"publisher","first-page":"863","DOI":"10.1287\/opre.11.6.863","volume":"11","author":"PC Gilmore","year":"1963","unstructured":"P. C. Gilmore and R. E. Gomory. A linear programming approach to the cutting stock problem\u2013(Part II). Oper. Res., 11: 863\u2013888, 1963.","journal-title":"Oper. Res"},{"key":"3_CR55","doi-asserted-by":"publisher","first-page":"403","DOI":"10.2307\/2311857","volume":"70","author":"SW Golomb","year":"1963","unstructured":"S. W. Golomb. On certain nonlinear recurring sequences. American Math. Monthly, 70: 403\u2013405, 1963.","journal-title":"American Math. Monthly"},{"issue":"45","key":"3_CR56","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"RL Graham","year":"1966","unstructured":"R. L. Graham. Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J., 45 (45): 1563\u20131581, 1966.","journal-title":"Bell Syst. Tech. J"},{"issue":"2","key":"3_CR57","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math., 17 (2): 263\u2013269, 1969.","journal-title":"Siam J. Appl. Math"},{"key":"3_CR58","doi-asserted-by":"crossref","unstructured":"R. L. Graham. Bounds on multiprocessing anomalies and related packing algorithms. In Proc. 1972 Spring Joint Computer Conf.,pages 205\u2013217, Montvale NJ, 1972. AFIPS Press.","DOI":"10.1145\/1478873.1478901"},{"key":"3_CR59","unstructured":"E. F. Grove. Online bin packing with lookahead. Unpublished manuscript, 1994."},{"key":"3_CR60","first-page":"1","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"LA Hall","year":"1997","unstructured":"L. A. Hall. Approximation algorithms for scheduling. In D. S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, pages 1\u201345. PWS Publ. Company, 1997."},{"key":"3_CR61","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D Hochbaum","year":"1987","unstructured":"D. Hochbaum and D. Shmoys. Using dual approximation algorithms for scheduling problems: theoretical and practical results. J. ACM, 34: 144\u2013162, 1987.","journal-title":"J. Acm"},{"key":"3_CR62","volume-title":"Approximation Algorithms for NP-Hard Problems. Pws Publ","author":"DS Hochbaum","year":"1997","unstructured":"D. S. Hochbaum. Approximation Algorithms for NP-Hard Problems. PWS Publ. Company, Boston, 1997."},{"key":"3_CR63","first-page":"389","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"DS Hochbaum","year":"1997","unstructured":"D. S. Hochbaum. Various notions of approximation: Good, better, best, and more. In D. S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, pages 389\u2013391. PWS Publ. Company, 1997."},{"key":"3_CR64","volume-title":"Analysis of Algorithms","author":"M Hofri","year":"1995","unstructured":"M. Hofri. Analysis of Algorithms. Oxford University Press, New York, 1995."},{"key":"3_CR65","first-page":"224","volume-title":"Proc. 1st European Symp. on Algorithms, volume 726 of Lecture Notes in Computer Science","author":"Z Ivkovi\u00e9","year":"1993","unstructured":"Z. Ivkovi\u00e9 and E. Lloyd. Fully dynamic algorithms for bin packing: being myopic helps. In Proc. 1st European Symp. on Algorithms, volume 726 of Lecture Notes in Computer Science, pages 224\u2013235. Springer Verlag, New York, 1993."},{"issue":"4","key":"3_CR66","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0020-0190(96)00112-3","volume":"59","author":"Z Ivkovi\u00e9","year":"1996","unstructured":"Z. Ivkovi\u00e9 and E. Lloyd. A fundamental restriction on fully dynamic maintenance of bin packing. Inf. Proc. Lett., 59 (4): 229\u2013232, 1996.","journal-title":"Inf. Proc. Lett"},{"issue":"1","key":"3_CR67","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0020-0190(97)00092-6","volume":"63","author":"Z Ivkovi\u00e9","year":"1997","unstructured":"Z. Ivkovi\u00e9 and E. Lloyd. Partially dynamic bin packing can be solved within 1 + e in (amortized) polylogarithmic time. Inf. Proc. Lett., 63 (1): 45\u201350, 1997.","journal-title":"Inf. Proc. Lett"},{"key":"3_CR68","volume-title":"Proc. 13th Ieee Symp. Switching and Automata Theory, pages 144-154, New York","author":"DS Johnson","year":"1972","unstructured":"D. S. Johnson. Fast allocation algorithms. In Proc. 13th IEEE Symp. Switching and Automata Theory, pages 144\u2013154, New York, 1972."},{"key":"3_CR69","volume-title":"Near-optimal bin packing algorithms. PhD thesis","author":"DS Johnson","year":"1973","unstructured":"D. S. Johnson. Near-optimal bin packing algorithms. PhD thesis, MIT, Cambridge, MA, 1973."},{"key":"3_CR70","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1016\/S0022-0000(74)80026-7","volume":"8","author":"DS Johnson","year":"1974","unstructured":"D. S. Johnson. Fast algorithms for bin packing. J. Comput. Syst. Sci., 8: 272\u2013314, 1974.","journal-title":"J. Comput. Syst. Sci"},{"key":"3_CR71","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0196-6774(82)90011-6","volume":"3","author":"DS Johnson","year":"1982","unstructured":"D. S. Johnson. The NP-completeness column: An ongoing guide. J. Algorithms, 3: 89\u201399, 1982.","journal-title":"J. Algorithms"},{"key":"3_CR72","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1137\/0203025","volume":"3","author":"DS Johnson","year":"1974","unstructured":"D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, and R. L. Graham. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput., 3: 256\u2013278, 1974.","journal-title":"Siam J. Comput"},{"key":"3_CR73","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1006\/jagm.1996.0019","volume":"20","author":"DR Karger","year":"1996","unstructured":"D. R. Karger, S. J. Phillips, and E. Torng. A better algorithm for an ancient scheduling problem. J. Algorithms, 20: 400\u2013430, 1996.","journal-title":"J. Algorithms"},{"key":"3_CR74","first-page":"312","volume-title":"Proc. 23rd Annual Ieee Symp. Found. Comput. Sci.","author":"N Karmarkar","year":"1982","unstructured":"N. Karmarkar and R. M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In Proc. 23rd Annual IEEE Symp. Found. Comput. Sci., pages 312\u2013320, 1982."},{"key":"3_CR75","volume-title":"An on-line alorithm for cardinality constrained bin packing problem","author":"H Kellerer","year":"1997","unstructured":"H. Kellerer and U. Pferschy. An on-line alorithm for cardinality constrained bin packing problem. Technical report, Universitaet Graz und TU Graz, 1997."},{"key":"3_CR76","volume-title":"Proc. 7th Annual ACM-SIAM Symp. Discr. Algorithms, pages 359-364, Philadelphia","author":"C Kenyon","year":"1996","unstructured":"C. Kenyon. Best-fit bin-packing with random order. In Proc. 7th Annual ACM-SIAM Symp. Discr. Algorithms, pages 359\u2013364, Philadelphia, 1996."},{"key":"3_CR77","unstructured":"S. Khanna. Private communication."},{"key":"3_CR78","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0166-218X(88)90089-3","volume":"22","author":"NG Kinnersley","year":"1988","unstructured":"N. G. Kinnersley and M. A. Langston. On-line variable sized bin packing. Discr. Appl. Math., 22: 143\u2013148, 1988.","journal-title":"Discr. Appl. Math"},{"issue":"4","key":"3_CR79","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1145\/321906.321917","volume":"22","author":"KL Krause","year":"1975","unstructured":"K. L. Krause, Y. Y. Shen, and H. D. Schwetman. Analysis of several task-scheduling algorithms for a model of multiprogramming computer systems. J. ACM, 22 (4): 522\u2013550, 1975.","journal-title":"J. Acm"},{"issue":"28","key":"3_CR80","first-page":"1982","volume":"22","author":"MA Langston","year":"2290","unstructured":"M. A. Langston. Improved 0\/1 interchanged scheduling. BIT, 22: 28 2290, 1982.","journal-title":"Bit"},{"key":"3_CR81","doi-asserted-by":"crossref","unstructured":"E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys. Sequencing and scheduling: algorithms and complexity. In S. C. Graves, A. H. G. Rinnooy Kan, and P. H. Zipkin, editors, Logistics of production and inventory,volume 4 of Handbooks in operations research and management science,pages 445\u2013522. North-Holland, Amsterdam, 1993.","DOI":"10.1016\/S0927-0507(05)80189-6"},{"key":"3_CR82","volume-title":"Technical Report 83-03-FC-02","author":"CC Lee","year":"1983","unstructured":"C. C. Lee and D. T. Lee. A new algorithm for on-line bin-packing. Technical Report 83\u201303-FC-02, Department of Electrical Engineering and computer Science Northwestern University, Evanston, IL, 1983."},{"issue":"3","key":"3_CR83","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1145\/3828.3833","volume":"32","author":"CC Lee","year":"1985","unstructured":"C. C. Lee and D. T. Lee. A simple on-line bin-packing algorithm. J. ACM, 32 (3): 562\u2013572, 1985.","journal-title":"J. Acm"},{"issue":"4","key":"3_CR84","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra","year":"1983","unstructured":"H. W. Lenstra, Jr. Integer programming with a fixed number of variables. Math. Oper. Res., 8 (4): 538\u2013548, 1983.","journal-title":"Math. Oper. Res"},{"issue":"2","key":"3_CR85","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/S0020-0190(80)90077-0","volume":"10","author":"FM Liang","year":"1980","unstructured":"F. M. Liang. A lower bound for on-line bin packing. Inform. Process. Lett., 10 (2): 76\u201379, 1980.","journal-title":"Inform. Process. Lett"},{"key":"3_CR86","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF02243816","volume":"50","author":"W Mao","year":"1993","unstructured":"W. Mao. Best-k-fit bin packing. Computing, 50: 265\u2013270, 1993.","journal-title":"Computing"},{"issue":"1","key":"3_CR87","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1137\/0222004","volume":"22","author":"W. Mao","year":"1993","unstructured":"W. Mao. Tight worst-case performance bounds for next-k-fit bin packing. SIAM J. Comput.,22(1):46\u201356, 1993","journal-title":"SIAM J. Comput."},{"issue":"4","key":"3_CR88","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0167-6377(85)90028-8","volume":"4","author":"CU Martel","year":"1985","unstructured":"C. U. Martel. A linear time bin-packing algorithm. Oper. Res. Lett., 4 (4): 189\u2013192, 1985.","journal-title":"Oper. Res. Lett"},{"key":"3_CR89","doi-asserted-by":"crossref","unstructured":"F. D. Murgolo. An efficient approximation scheme for variable-sized bin packing. SIAM J. Comput.16(1):149\u2013161 1987.","DOI":"10.1137\/0216012"},{"key":"3_CR90","doi-asserted-by":"crossref","unstructured":"F. D. Murgolo. Anomalous behaviour in bin packing algorithms. Discr. Appl. Math. 21:229\u2013243 1988.","DOI":"10.1016\/0166-218X(88)90069-8"},{"key":"3_CR91","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0196-6774(89)90031-X","volume":"10","author":"P Ramanan","year":"1989","unstructured":"P. Ramanan, D. J. Brown, C. C. Lee, and D. T. Lee. On-line bin packing in linear time. J. Algorithms, 10: 305\u2013326, 1989.","journal-title":"J. Algorithms"},{"key":"3_CR92","doi-asserted-by":"crossref","unstructured":"M. B. Richey. Improved bounds for harmonic-based bin packing algorithms.Discr. Appl. Math. 34:203\u2013227 1991.","DOI":"10.1016\/0166-218X(91)90087-D"},{"key":"3_CR93","doi-asserted-by":"crossref","unstructured":"S. Sahni. Algorithms for scheduling independent tasks. J. ACM 23:116\u2013127 1976.","DOI":"10.1145\/321921.321934"},{"key":"3_CR94","doi-asserted-by":"crossref","unstructured":"H. E. Salzer. The approximation of number as sums of reciprocals. American Math. Monthly 54:135\u2013142 1947.","DOI":"10.1080\/00029890.1947.11991798"},{"key":"3_CR95","doi-asserted-by":"crossref","unstructured":"D. Simchi-Levi. New worst-case results for the bin packing problem. Naval Res. Log. Quart. 41:579\u2013585 1994.","DOI":"10.1002\/1520-6750(199406)41:4<579::AID-NAV3220410409>3.0.CO;2-G"},{"key":"3_CR96","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0020-0190(92)90223-I","volume":"43","author":"A Vliet","year":"1992","unstructured":"A. van Vliet. An improved lower bound for on-line bin packing algorithms. Inform. Process. Lett., 43: 277\u2013284, 1992.","journal-title":"Inform. Process. Lett"},{"key":"3_CR97","unstructured":"A. van Vliet. Lower and Upper Bounds for On-line Bin Packing and Scheduling Heuristic. PhD thesis, Erasmus University, Rotterdam, 1995."},{"key":"3_CR98","doi-asserted-by":"crossref","unstructured":"A. van Vliet. On the asymptotic worst case behavoir of harmonic fit. J. Algorithms 20:113\u2013136 1996.","DOI":"10.1006\/jagm.1996.0005"},{"issue":"2","key":"3_CR99","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/0167-6377(82)90046-3","volume":"1","author":"T.S. Wee","year":"1982","unstructured":"T. S. Wee and M. J. Magazine. Assembly line balancing as generalized bin packing. Oper. Res. Lett.,1(2):56\u201358, 1982.","journal-title":"Operations Research Letters"},{"key":"3_CR100","doi-asserted-by":"crossref","unstructured":"G. J. Woeginger. Improved space for bounded-space on-line bin-packing. SIAM J. Discr. Math. 6:575\u2013581 1993.","DOI":"10.1137\/0406045"},{"key":"3_CR101","unstructured":"K. Xu. A bin-packing problem with Item Sizes in the Interval (0, a] for G 2. PhD thesis, Chinese Academy of Sciences, Institute of Applied Mathematics, Beijing, China, 1993."},{"key":"3_CR102","doi-asserted-by":"crossref","unstructured":"A. C.-C. Yao. New algorithms for bin packing. J. ACM 27(2):207\u2013227 1980.","DOI":"10.1145\/322186.322187"},{"key":"3_CR103","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/BF02216826","volume":"24","author":"M Yue","year":"1991","unstructured":"M. Yue. On the exact upper bound for the multifit processor scheduling algorithm. Ann. Oper. Res., 24: 233\u2013259, 1991.","journal-title":"Ann. Oper. Res"},{"issue":"4","key":"3_CR104","first-page":"321331","volume":"7","author":"M. Yue","year":"1991","unstructured":"M. Yue. A simple proof of the inequality FFD(L) OPT (L) + 1 dL for the FFD bin packing algorithm. Acta Math. App. Sinica,7(4):321331, 1991.","journal-title":"Acta Math. App. Sinica"},{"key":"3_CR105","unstructured":"G. Zhang. Tight worst-case performance bound for AFBk. Technical Report 15, Inst. of Applied Mathematics. Academia Sinica, Beijng, China, 1994."},{"key":"3_CR106","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/BF02309343","volume":"56","author":"G Zhang","year":"1996","unstructured":"G. Zhang. Worst-case analysis of the FFH algorithm for on-line variable-sized bin paking. Computing, 56: 165\u2013172, 1996.","journal-title":"Computing"},{"key":"3_CR107","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/S0166-218X(96)00018-2","volume":"72","author":"G Zhang","year":"1997","unstructured":"G. Zhang. A new version of on-line variable-sized bin packing. Discr. Appl. Math., 72: 193\u2013197, 1997.","journal-title":"Discr. Appl. Math"}],"container-title":["Handbook of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4757-3023-4_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T21:52:10Z","timestamp":1745963530000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4757-3023-4_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9781441948137","9781475730234"],"references-count":107,"URL":"https:\/\/doi.org\/10.1007\/978-1-4757-3023-4_3","relation":{},"subject":[],"published":{"date-parts":[[1999]]}}}