{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T21:48:07Z","timestamp":1773092887092,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1993,3,1]],"date-time":"1993-03-01T00:00:00Z","timestamp":730944000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1993,3]]},"DOI":"10.1007\/bf01190899","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T06:57:59Z","timestamp":1108709879000},"page":"253-277","source":"Crossref","is-referenced-by-count":31,"title":["Packings in two dimensions: Asymptotic average-case analysis of algorithms"],"prefix":"10.1007","volume":"9","author":[{"suffix":"Jr.","given":"E. G.","family":"Coffman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P. W.","family":"Shor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01190899_CR1","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1137\/0212033","volume":"12","author":"B. S. Baker","year":"1983","unstructured":"Baker, B. S., and Schwarz, J. S., Shelf Algorithms for Two-Dimensional Packing Problems,SIAM J. Comput.,12 (1983), 508\u2013525.","journal-title":"SIAM J. Comput."},{"key":"BF01190899_CR2","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0167-6377(89)90026-6","volume":"8","author":"J. J. Bartholdi","year":"1989","unstructured":"Bartholdi, J. J., Vande Vate, J. H., and Zhang, J., Expected Performance of the Shelf Heuristic for Two-Dimensional Packing,Oper. Res. Lett.,8 (1989), 11\u201316.","journal-title":"Oper. Res. Lett."},{"key":"BF01190899_CR3","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/0304-4149(90)90098-D","volume":"36","author":"E. G. Coffman Jr.","year":"1990","unstructured":"Coffman, E. G., Jr., Flatto, L., and Leighton, F. T., First-Fit Allocation of Queues: Tight Probabilistic Bounds on Wasted Space,Stochastic Process Appl.,36 (1990), 311\u2013330.","journal-title":"Stochastic Process Appl."},{"key":"BF01190899_CR4","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1137\/0212014","volume":"12","author":"E. G. Coffman Jr.","year":"1983","unstructured":"Coffman, E. G., Jr., Garey, M. R., and Johnson, D. S., Dynamic Bin Packing,SIAM J. Comput.,12 (1983), 227\u2013258.","journal-title":"SIAM J. Comput."},{"key":"BF01190899_CR5","first-page":"49","volume-title":"Algorithm Design for Computer System Design","author":"E. G. Coffman Jr.","year":"1984","unstructured":"Coffman, E. G., Jr., Garey, M. R., and Johnson, D. S., Approximation Algorithms for Bin Packing-An Updated Survey,Algorithm Design for Computer System Design (G. Ausiello, M. Lucertini, and P. Serafini, eds.), Springer-Verlag, New York, 1984, pp. 49\u2013106."},{"key":"BF01190899_CR6","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1137\/0209062","volume":"9","author":"E. G. Coffman Jr.","year":"1980","unstructured":"Coffman, E. G., Jr., Garey, M. R., Johnson, D. S., and Tarjan, R. E., Performance Bounds for Level Oriented Two-Dimensional Packing Algorithms,SIAM J. Comput.,9 (1980), 808\u2013826.","journal-title":"SIAM J. Comput."},{"key":"BF01190899_CR7","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0218011","volume":"18","author":"E. G. Coffman Jr.","year":"1989","unstructured":"Coffman, E. G., Jr., and Lagarias, J. C., Algorithms for Packing Squares: A Probabilistic Analysis,SIAM J. Comput.,18 (1989), 166\u2013185.","journal-title":"SIAM J. Comput."},{"key":"BF01190899_CR8","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/0022-0000(89)90031-7","volume":"38","author":"E. G. Coffman Jr.","year":"1989","unstructured":"Coffman, E. G., Jr., and Leighton, F. T., A Provably Efficient Algorithm for Dynamic Storage Allocation,J. Comput. System Sci.,38 (1989), 2\u201335.","journal-title":"J. Comput. System Sci."},{"key":"BF01190899_CR9","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1287\/mnsc.34.3.266","volume":"34","author":"E. G. Coffman Jr.","year":"1988","unstructured":"Coffman, E. G., Jr., Lueker, G. S., and Rinnooy Kan, A., Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics,Management Sci.,34 (1988), 266\u2013290.","journal-title":"Management Sci."},{"key":"BF01190899_CR10","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/S0019-9958(80)90050-9","volume":"44","author":"E. G. Coffman Jr.","year":"1980","unstructured":"Coffman, E. G., Jr., So, K., Hofri, M., and Yao, A. C., A Stochastic Model of Bin Packing,Inform, and Control,44 (1980), 105\u2013115.","journal-title":"Inform, and Control"},{"key":"BF01190899_CR11","volume-title":"Regional Conference Series in Applied Mathematics","author":"J. Durbin","year":"1973","unstructured":"Durbin, J.,Distribution Theory for Tests Based on the Sample Distribution Function, Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, PA, 1973."},{"key":"BF01190899_CR12","volume-title":"An Introduction to Probability Theory and Its Applications, Vol. I","author":"W. Feller","year":"1968","unstructured":"Feller, W.,An Introduction to Probability Theory and Its Applications, Vol. I, 3rd edn., Wiley, New York, 1968.","edition":"3rd edn."},{"key":"BF01190899_CR13","volume-title":"An Introduction to Probability Theory and Its Applications, Vol. II","author":"W. Feller","year":"1971","unstructured":"Feller, W.,An Introduction to Probability Theory and Its Applications, Vol. II, 2nd edn., Wiley, New York, 1971.","edition":"2nd edn."},{"key":"BF01190899_CR14","volume-title":"Next-Fit Bin Packing with Random Piece Sizes, Technical Report","author":"S. Halfin","year":"1989","unstructured":"Halfin, S., Next-Fit Bin Packing with Random Piece Sizes, Technical Report, Bell Communications Research, Morristown, NJ, 1989."},{"key":"BF01190899_CR15","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"Hoeffding, W., Probability Inequalities for Sums of Bounded Random Variables,Amer. Statist. Assoc. J.,58 (1963), 13\u201330.","journal-title":"Amer. Statist. Assoc. J."},{"key":"BF01190899_CR16","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/BF02241699","volume":"29","author":"U. Hoffman","year":"1982","unstructured":"Hoffman, U., A Class of Simple Stochastic On-Line Bin-Packing Algorithms,Computing,29 (1982), 227\u2013239.","journal-title":"Computing"},{"key":"BF01190899_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(80)90817-7","volume":"45","author":"M. Hofri","year":"1980","unstructured":"Hofri, M., Two-Dimensional Packing: Expected Performance of Simple Level Algorithms,Inform. and Control,45 (1980), 1\u201317.","journal-title":"Inform. and Control"},{"key":"BF01190899_CR18","doi-asserted-by":"crossref","unstructured":"Karmarkar, N, Probabilistic Analysis of Some Bin-Packing Algorithms,Proc. 23rd IEEE Sympon. Foundations of Computer Science, 1982, pp. 107\u2013111.","DOI":"10.1109\/SFCS.1982.37"},{"key":"BF01190899_CR19","doi-asserted-by":"crossref","unstructured":"Karp, R. M., Luby, M., and Marchetti-Spaccamela, A., Probabilistic Analysis of Muiti-Dimensional Bin-Packing Problems,Proc. 16th ACM Symp, on Theory of Computing, 1984, pp. 289\u2013298.","DOI":"10.1145\/800057.808693"},{"key":"BF01190899_CR20","volume-title":"Technical Report","author":"C. C. Lee","year":"1989","unstructured":"Lee, C. C., and Lee, D. T., Robust On-Line Packing Algorithms, Technical Report, Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL, 1989."},{"key":"BF01190899_CR21","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF02124678","volume":"9","author":"F. T. Leighton","year":"1989","unstructured":"Leighton, F. T., and Shor, P. W., Tight Bounds for Minimax Grid Matching, with Applications to the Average-Case Analysis of Algorithms,Combinatorica,9 (1989), 161\u2013187.","journal-title":"Combinatorica"},{"key":"BF01190899_CR22","volume-title":"Technical Report 181","author":"G. S. Lueker","year":"1982","unstructured":"Lueker, G. S., An Average-Case Analysis of Bin-Packing with Uniformly Distributed Item Sizes, Technical Report 181, University of California at Irvine, CA, 1982."},{"key":"BF01190899_CR23","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1007\/BF01553906","volume":"4","author":"P. Ramanan","year":"1989","unstructured":"Ramanan, P., and Tsuga, K., Average-Case Analysis of the Modified Harmonic Algorithm,Algorithmic,4 (1989), 519\u2013533.","journal-title":"Algorithmic"},{"key":"BF01190899_CR24","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/BF02579171","volume":"6","author":"P. W. Shor","year":"1986","unstructured":"Shor, P. W., The Average-Case Analysis of Some On-Line Algorithms for Bin Packing,Combinatorica,6 (1986), 179\u2013200.","journal-title":"Combinatorica"},{"key":"BF01190899_CR25","unstructured":"Shor, P. W., How To Do Better than Best Fit: An Improved On-Line Bin Packing Algorithm, AT&T Bell Laboratories, Murray Hill, NJ (to appear)."},{"key":"BF01190899_CR26","volume-title":"Technical Report","author":"M. Talagrand","year":"1992","unstructured":"Talagrand, M., Technical Report, Mathematics Department, Ohio State University, Columbus, OH, 1992."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01190899.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01190899\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01190899","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01190899.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,17]],"date-time":"2020-02-17T17:53:49Z","timestamp":1581962029000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01190899"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,3]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1993,3]]}},"alternative-id":["BF01190899"],"URL":"https:\/\/doi.org\/10.1007\/bf01190899","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,3]]}}}