{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:56:09Z","timestamp":1773798969097,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1986,6,1]],"date-time":"1986-06-01T00:00:00Z","timestamp":517968000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1986,6]]},"DOI":"10.1007\/bf02579171","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T21:15:33Z","timestamp":1174598133000},"page":"179-200","source":"Crossref","is-referenced-by-count":63,"title":["The average-case analysis of some on-line algorithms for bin packing"],"prefix":"10.1007","volume":"6","author":[{"given":"Peter W.","family":"Shor","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF02579171_CR1","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF02579135","volume":"4","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai, J. Koml\u00f3s andG. Tusn\u00e1dy, On optimal matchings,Combinatorica 4 (1983), 259\u2013264.","journal-title":"Combinatorica"},{"key":"BF02579171_CR2","first-page":"51","volume-title":"Proc. 21st Ann. Allerton Conf. on Communication, Control, and Computing","author":"J. L. Bentley","year":"1983","unstructured":"J. L. Bentley, D. S. Johnson, F. T. Leighton andC. C. McGeoch, An experimental study of bin packing,Proc. 21st Ann. Allerton Conf. on Communication, Control, and Computing, University of Illinois, Urbana IL, (1983), 51\u201360."},{"key":"BF02579171_CR3","doi-asserted-by":"crossref","unstructured":"J. L. Bentley, D. S. Johnson, F. T. Leighton, C. C. McGeoch andL. McGeoch, Some unexpected expected behavior results for bin packing,Proc. 16th ACM Symp. on Theory of Computing, (1984), 279\u2013288.","DOI":"10.1145\/800057.808692"},{"key":"BF02579171_CR4","unstructured":"J. L. Bentley andC. C. McGeoch,personal communications."},{"key":"BF02579171_CR5","unstructured":"D. J. Brown, A lower bound for on-line one-dimensional bin packing algorithms,Technical Report R 86,Coordinated Science Lab., U. of Illinois, Urbana, IL, 1979."},{"key":"BF02579171_CR6","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/978-3-7091-4338-4_3","volume-title":"Algorithm Design for Computer System Design","author":"E. G. Coffman Jr.","year":"1984","unstructured":"E. G. Coffman, Jr., M. R. Garey andD. S. Johnson, Approximation algorithms for bin packing \u2014 an updated survey,Algorithm Design for Computer System Design, (G. Ausiello, M. Lucertini and P. Serafini, eds.), Springer\u2014Verlag, New York, (1984), 49\u2013106."},{"key":"BF02579171_CR7","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":"E. G. Coffman, Jr., M. Hofri, K. So andA. C. Yao, A stochastic model of bin packing,Information and Control 44 (1980), 105\u2013115.","journal-title":"Information and Control"},{"key":"BF02579171_CR8","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/BF00539835","volume":"61","author":"R. M. Dudley","year":"1982","unstructured":"R. M. Dudley, Empirical and Poisson processes on classes of sets or functions too large for central limit theorems,Z. Wahrsch. verw. Gebiete 61 (1982), 355\u2013368.","journal-title":"Z. Wahrsch. verw. Gebiete"},{"key":"BF02579171_CR9","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W. Fernandez Vega de la","year":"1981","unstructured":"W. Fernandez de la Vega andG. S. Lueker, Bin packing can be solved within 1 +\u03b5 in linear time,Combinatorica 1 (1981), 349\u2013355.","journal-title":"Combinatorica"},{"key":"BF02579171_CR10","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/0020-0190(80)90041-1","volume":"11","author":"G. N. Frederickson","year":"1980","unstructured":"G. N. Frederickson, Probabilistic analysis for simple one- and two-dimensional bin packing algorithms,Inf. Proc. Letters 11 (1980), 156\u2013161.","journal-title":"Inf. Proc. Letters"},{"key":"BF02579171_CR11","first-page":"345","volume":"1","author":"J. M. Hammersley","year":"1970","unstructured":"J. M. Hammersley, A few seedlings of research,Proc. 6th Berkeley Symp. on Mathematical Statistics and Probability,1 (1970), 345\u2013394.","journal-title":"Proc. 6th Berkeley Symp. on Mathematical Statistics and Probability"},{"key":"BF02579171_CR12","unstructured":"D. S. Johnson,Near-optimal bin packing algorithms, Ph. D. Thesis, Massachusetts Institute of Technology, June 1973, Project MAC TR\u2014109."},{"key":"BF02579171_CR13","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1137\/0203025","volume":"3","author":"D. S. Johnson","year":"1974","unstructured":"D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey andR. L. Graham, Worst-case performance bounds for simple one-dimensional packing algorithms,SIAM J. of Computing 3 (1974), 299\u2013325.","journal-title":"SIAM J. of Computing"},{"key":"BF02579171_CR14","doi-asserted-by":"crossref","unstructured":"N. Karmarkar, Probabilistic analysis of some bin-packing algorithms,Proc. 23rd IEEE Symp. on Foundations of Computer Science, (1982), 107\u2013111.","DOI":"10.1109\/SFCS.1982.37"},{"key":"BF02579171_CR15","doi-asserted-by":"crossref","unstructured":"N. Karmarkar andR. M. Karp, An efficient approximation scheme for the one-dimensional bin packing problem,Proc. 23rd IEEE Symp. on Foundations of Computer Science, (1982), 312\u2013320.","DOI":"10.1109\/SFCS.1982.61"},{"key":"BF02579171_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/3-540-10856-4_104","volume-title":"Mathematical Foundations of Computer Science 1981","author":"W. Kn\u00f6del","year":"1981","unstructured":"W. Kn\u00f6del, A bin packing algorithm with complexity 0 (n logn) and performance 1 in the stochastic limit,Mathematical Foundations of Computer Science 1981, Lecture Notes in Computer Science 118, (J. Gruska and M. Chytil, eds.), Springer, Berlin, (1981), 369\u2013378."},{"key":"BF02579171_CR17","doi-asserted-by":"crossref","unstructured":"R. M. Karp, M. Luby andA. Marchetti-Spaccamela, Probabilistic analysis of multi-dimensional bin packing problems,Proc. 16th ACM Symp. on Theory of Computing, (1984), 289\u2013298.","DOI":"10.1145\/800057.808693"},{"key":"BF02579171_CR18","doi-asserted-by":"crossref","unstructured":"F. T. Leighton andC. E. Leiserson, Wafer-scale integration of systolic arrays,Proc. 23rd IEEE Symp. on Foundations of Computer Science, (1982), 297\u2013311.","DOI":"10.1109\/SFCS.1982.49"},{"key":"BF02579171_CR19","doi-asserted-by":"crossref","unstructured":"F. T. Leighton andP. W. Shor, Tight bounds for minimax grid matching, with applications to the average case analysis of algorithms.Proc. 18th ACM Symp. on Theory of Computing, (1986), 91\u2013103.","DOI":"10.1145\/12130.12140"},{"key":"BF02579171_CR20","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/S0020-0190(80)90077-0","volume":"10","author":"F. M. Liang","year":"1980","unstructured":"F. M. Liang, A lower bound for on-line bin packing,Inf. Proc. Letters 10 (1980), 76\u201379.","journal-title":"Inf. Proc. Letters"},{"key":"BF02579171_CR21","doi-asserted-by":"crossref","unstructured":"G. S. Lueker, An average-case analysis of bin packing with uniformly distributed item sizes,report No. 181, Department of Information and Computer Science, U. of California, Irvine, CA, 1982.","DOI":"10.1109\/SFCS.1983.9"},{"key":"BF02579171_CR22","unstructured":"G. S. Lueker, personal communication."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579171.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02579171\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579171","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T04:22:16Z","timestamp":1683778936000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02579171"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,6]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1986,6]]}},"alternative-id":["BF02579171"],"URL":"https:\/\/doi.org\/10.1007\/bf02579171","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,6]]}}}