{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T03:25:57Z","timestamp":1743132357652,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":24,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387307701"},{"type":"electronic","value":"9780387301624"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_49","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T18:36:37Z","timestamp":1214505397000},"page":"94-97","source":"Crossref","is-referenced-by-count":2,"title":["Bin Packing"],"prefix":"10.1007","author":[{"given":"David S.","family":"Johnson","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"49_CR1_49","unstructured":"Bentley, J.L., Johnson, D.S., Leighton, F.T., McGeoch, C.C.: An experimental study of bin packing. In: Proc. of the 21st Annual Allerton Conference on Communication, Control, and Computing, Urbana, University of Illinois, 1983 pp.\u00a051\u201360"},{"key":"49_CR2_49","first-page":"279","volume-title":"Proc. of the 16th Annual ACM Symposium on Theory of Computing","author":"J.L. Bentley","year":"1984","unstructured":"Bentley, J.L., Johnson, D.S., Leighton, F.T., McGeoch, C.C., McGeoch, L.A.: Some unexpected expected behavior results for bin packing. In: Proc. of the 16th Annual ACM Symposium on Theory of Computing, pp. 279\u2013288. ACM, New York (1984)"},{"key":"49_CR3_49","first-page":"230","volume-title":"Proc. of the 23rd Annual ACM Symposium on Theory of Computing, New York, 1991","author":"E.G. Coffman Jr","year":"1991","unstructured":"Coffman Jr, E.G., Courcoubetis, C., Garey, M.R., Johnson, D.S., McGeoch, L.A., Shor, P.W., Weber, R.R., Yannakakis, M.: Fundamental discrepancies between average-case analyses under discrete and continuous distributions. In: Proc. of the 23rd Annual ACM Symposium on Theory of Computing, New York, 1991, pp.\u00a0230\u2013240. ACM Press, New York (1991)"},{"key":"49_CR4_49","first-page":"46","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"E.G. Coffman Jr.","year":"1997","unstructured":"Coffman Jr., E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin-packing: A survey. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-Hard Problems, pp. 46\u201393. PWS Publishing, Boston (1997)"},{"key":"49_CR5_49","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<69::AID-RSA4>3.0.CO;2-V","volume":"10","author":"E.G. Coffman Jr.","year":"1997","unstructured":"Coffman Jr., E.G., Johnson, D.S., Shor, P.W., Weber, R.R.: Bin packing with discrete item sizes, part\u00a0II: Tight bounds on first fit. Random Struct. Algorithms 10, 69\u2013101 (1997)","journal-title":"Random Struct. Algorithms"},{"key":"49_CR6_49","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/S0019-9958(80)90050-9","volume":"44","author":"E.G. Coffman Jr.","year":"1980","unstructured":"Coffman Jr., E.G., So, K., Hofri, M., Yao, A.C.: A stochastic model of bin-packing. Inf. Cont. 44, 105\u2013115 (1980)","journal-title":"Inf. Cont."},{"key":"49_CR7_49","doi-asserted-by":"publisher","first-page":"989","DOI":"10.2307\/3214471","volume":"23","author":"C. Courcoubetis","year":"1986","unstructured":"Courcoubetis, C., Weber, R.R.: Necessary and sufficient conditions for stability of a bin packing system. J.\u00a0Appl. Prob. 23, 989\u2013999 (1986)","journal-title":"J. Appl. Prob."},{"key":"49_CR8_49","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s00453-001-0041-7","volume":"31","author":"J. Csirik","year":"2001","unstructured":"Csirik, J., Johnson, D.S.: Bounded space on-line bin packing: Best is better than first. Algorithmica 31, 115\u2013138 (2001)","journal-title":"Algorithmica"},{"key":"49_CR9_49","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1120582.1120583","volume":"53","author":"J. Csirik","year":"2006","unstructured":"Csirik, J., Johnson, D.S., Kenyon, C., Orlin, J.B., Shor, P.W., Weber, R.R.: On the sum-of-squares algorithm for bin packing. J.\u00a0ACM 53, 1\u201365 (2006)","journal-title":"J. ACM"},{"key":"49_CR10_49","first-page":"246","volume-title":"Proc. of the 1999 Workshop on Algorithm Engineering and Experimentation. LNCS, vol. 1619","author":"J. Csirik","year":"1999","unstructured":"Csirik, J., Johnson, D.S., Kenyon, C., Shor, P.W., Weber, R.R.: A self organizing bin packing heuristic. In: Proc. of the 1999 Workshop on Algorithm Engineering and Experimentation. LNCS, vol.\u00a01619, pp. 246\u2013265. Springer, Berlin (1999)"},{"key":"49_CR11_49","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF01415672","volume":"42","author":"G. Galambos","year":"1995","unstructured":"Galambos, G., Woeginger, G.J.: Online bin packing\u00a0\u2013 a restricted survey. ZOR Math. Methods Oper. Res. 42, 25\u201345 (1995)","journal-title":"ZOR Math. Methods Oper. Res."},{"key":"49_CR12_49","unstructured":"Johnson, D.S.: Near-Optimal Bin Packing Algorithms. Ph.\u202fD. thesis, Massachusetts Institute of Technology, Department of Mathematics, Cambridge (1973)"},{"key":"49_CR13_49","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1137\/0203025","volume":"3","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R., Graham, R.L.: Worst-case performance bounds for simple one\u2010dimensional packing algorithms. SIAM J.\u00a0Comput. 3, 299\u2013325 (1974)","journal-title":"SIAM J. Comput."},{"key":"49_CR14_49","unstructured":"Johnson, D.S., Leighton, F.T., Shor, P.W., Weber, R.R.: The expected behavior of FFD, BFD, and optimal bin packing under $$ { U(0,\\alpha]) } $$ distributions (in preparation)"},{"key":"49_CR15_49","first-page":"312","volume-title":"Proc. of the 23rd Annual Symposium on Foundations of Computer Science","author":"N. Karmarkar","year":"1982","unstructured":"Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one\u2010dimensional bin packing problem. In: Proc. of the 23rd Annual Symposium on Foundations of Computer Science, pp. 312\u2013320. IEEE Computer Soc, Los Alamitos, CA (1982)"},{"key":"49_CR16_49","first-page":"369","volume-title":"Proc. 10th Symp. on Mathematical Foundations of Computer Science. LNCS, vol. 118","author":"W. Kn\u00f6del","year":"1981","unstructured":"Kn\u00f6del, W.: A bin packing algorithm with complexity $$ { {O}(n log n) } $$ in the stochastic limit. In: Proc. 10th Symp. on Mathematical Foundations of Computer Science. LNCS, vol.\u00a0118, pp. 369\u2013378. Springer, Berlin (1981)"},{"key":"49_CR17_49","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1145\/3828.3833","volume":"32","author":"C.C. Lee","year":"1985","unstructured":"Lee, C.C., Lee, D.T.: A simple on-line packing algorithm. J.\u00a0ACM 32, 562\u2013572 (1985)","journal-title":"J. ACM"},{"key":"49_CR18_49","volume-title":"Robust on-line bin packing algorithms. Tech. Rep","author":"C.C. Lee","year":"1987","unstructured":"Lee, C.C., Lee, D.T.: Robust on-line bin packing algorithms. Tech. Rep. Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL (1987)"},{"key":"49_CR19_49","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF02124678","volume":"9","author":"T. Leighton","year":"1989","unstructured":"Leighton, T., Shor, P.: Tight bounds for minimax grid matching with applications to the average case analysis of algorithms. Combinatorica 9 161\u2013187 (1989)","journal-title":"Combinatorica"},{"key":"49_CR20_49","doi-asserted-by":"crossref","unstructured":"Lueker, G.S.: An average-case analysis of bin packing with uniformly distributed item sizes. Tech. Rep. Report No 181, Dept. of Information and Computer Science, University of California, Irvine, CA (1982)","DOI":"10.1109\/SFCS.1983.9"},{"key":"49_CR21_49","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1145\/585265.585269","volume":"49","author":"S.S. Seiden","year":"2002","unstructured":"Seiden, S.S.: On the online bin packing problem. J.\u00a0ACM 49, 640\u2013671 (2002)","journal-title":"J. ACM"},{"key":"49_CR22_49","unstructured":"Ullman, J.D.: The performance of a memory allocation algorithm. Tech. Rep. 100, Princeton University, Princeton, NJ (1971)"},{"key":"49_CR23_49","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0020-0190(92)90223-I","volume":"43","author":"A. van Vliet","year":"1992","unstructured":"van Vliet, A.: An improved lower bound for on-line bin packing algorithms. Inf. Proc. Lett. 43, 277\u2013284 (1992)","journal-title":"Inf. Proc. Lett."},{"key":"49_CR24_49","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1145\/322186.322187","volume":"27","author":"A.C. Yao","year":"1980","unstructured":"Yao, A.C.: New algorithms for bin packing. J.\u00a0ACM 27, 207\u2013227 (1980)","journal-title":"J. ACM"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_49","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,27]],"date-time":"2024-02-27T22:07:33Z","timestamp":1709071653000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_49"}},"subtitle":["1997; Coffman, Garay, Johnson"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_49","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}