{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:11:15Z","timestamp":1725484275206},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540439967"},{"type":"electronic","value":"9783540456551"}],"license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45655-4_50","type":"book-chapter","created":{"date-parts":[[2007,5,21]],"date-time":"2007-05-21T07:37:01Z","timestamp":1179733021000},"page":"467-475","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On-Line Maximizing the Number of Items Packed in Variable-Sized Bins"],"prefix":"10.1007","author":[{"given":"Leah","family":"Epstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lene M.","family":"Favrholdt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,8,29]]},"reference":[{"issue":"3","key":"50_CR1","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1145\/258128.258201","volume":"44","author":"J. Aspnes","year":"1997","unstructured":"J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, and O. Waarts. On-Line Routing of Virtual Circuits with Applications to Load Balancing and Machine Scheduling. Journal of the ACM, 44(3):486\u2013504, 1997. Also in Proc. 25th ACM STOC, 1993, pp. 623-631.","journal-title":"Journal of the ACM"},{"key":"50_CR2","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1016\/0196-6774(84)90004-X","volume":"5","author":"S. F. Assmann","year":"1984","unstructured":"S. F. Assmann, D. S. Johnson, D. J. Kleitman, and J. Y. Leung. On a Dual Version of the One-Dimensional Bin Packing Problem. Journal of Algorithms, 5:502\u2013525, 1984.","journal-title":"Journal of Algorithms"},{"key":"50_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/3-540-44985-X_18","volume-title":"Algorithmica (to appear)","author":"Y. Azar","year":"2000","unstructured":"Y. Azar, J. Boyar, L. Epstein, L. M. Favrholdt, K. S. Larsen, and M. N. Nielsen. Fair versus Unrestricted Bin Packing. Algorithmica (to appear). Preliminary version at SWAT 2000, volume 1851 of LNCS: 200\u2013213, Springer-Verlag, 2000."},{"key":"50_CR4","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1006\/jagm.1999.1070","volume":"35","author":"P. Berman","year":"2000","unstructured":"P. Berman, M. Charikar, and M. Karpinski. On-Line Load Balancing for Related Machines. Journal of Algorithms, 35:108\u2013121, 2000.","journal-title":"Journal of Algorithms"},{"key":"50_CR5","unstructured":"A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998."},{"key":"50_CR6","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/PL00009286","volume":"25","author":"J. Boyar","year":"1999","unstructured":"J. Boyar and K. S. Larsen. The Seat Reservation Problem. Algorithmica, 25:403\u2013417, 1999","journal-title":"Algorithmica"},{"issue":"1","key":"50_CR7","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1137\/S0097539799361786","volume":"31","author":"J. Boyar","year":"2001","unstructured":"J. Boyar, K. S. Larsen, and M. N. Nielsen. The Accommodating Function: A Generalization of the Competitive Ratio. SIAM Journal on Computing, 31(1):233\u2013258, 2001.","journal-title":"SIAM Journal on Computing"},{"key":"50_CR8","first-page":"333","volume":"22","author":"J. L. Bruno","year":"1985","unstructured":"J. L. Bruno and P. J. Downey. Probabilistic Bounds for Dual Bin-Packing. Acta Informatica, 22:333\u2013345, 1985.","journal-title":"Acta Informatica"},{"key":"50_CR9","unstructured":"C. Chekuri and S. Khanna. A PTAS for the Multiple Knapsack Problem. In Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 213\u2013222, 2000."},{"key":"50_CR10","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/0209007","volume":"9","author":"Y. Cho","year":"1988","unstructured":"Y. Cho and S. Sahni. Bounds for List Schedules on Uniform Processors. SIAM Journal on Computing, 9:91\u2013103, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"50_CR11","unstructured":"E. G. Coffman, Jr., M. R. Garey, and D. S. Johnson. Approximation Algorithms for Bin Packing: A Survey. In Dorit S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, chapter 2, pages 46\u201393. PWS Publishing Company, 1997."},{"key":"50_CR12","first-page":"87","volume":"1","author":"J. Csirik","year":"1990","unstructured":"J. Csirik and J. B. G. Frenk. A Dual Version of Bin Packing. Algorithms Review, 1:87\u201395, 1990.","journal-title":"Algorithms Review"},{"key":"50_CR13","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. On-Line Algorithms for a Dual Version of Bin Packing. Discr. Appl. Math., 21:163\u2013167, 1988.","journal-title":"Discr. Appl. Math"},{"key":"50_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BFb0029568","volume-title":"Online Algorithms","author":"J. Csirik","year":"1998","unstructured":"J. Csirik and G. Woeginger. On-Line Packing and Covering Problems. In Amos Fiat and Gerhard J. Woeginger, editors, Online Algorithms, volume 1442 of LNCS, chapter 7, pages 147\u2013177. Springer-Verlag, 1998."},{"key":"50_CR15","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R. L. Graham","year":"1966","unstructured":"R. L. Graham. Bounds for Certain Multiprocessing Anomalies. Bell Systems Technical Journal, 45:1563\u20131581, 1966.","journal-title":"Bell Systems Technical Journal"},{"issue":"2","key":"50_CR16","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1137\/0208016","volume":"8","author":"E. G. Coffman Jr","year":"1979","unstructured":"E. G. Coffman Jr. and J. Y. Leung. Combinatorial Analysis of an Efficient Algorithm for Processor and Storage Allocation. SIAM Journal on Computing, 8(2):202\u2013217, 1979.","journal-title":"SIAM Journal on Computing"},{"key":"50_CR17","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF00288885","volume":"9","author":"E. G. Coffman Jr","year":"1978","unstructured":"E. G. Coffman Jr. J. Y. Leung, and D. W. Ting. Bin Packing: Maximizing the Number of Pieces Packed. Acta Informatica, 9:263\u2013271, 1978.","journal-title":"Acta Informatica"},{"key":"50_CR18","unstructured":"J. Y. Leung. Fast Algorithms for Packing Problems. PhD thesis, Pennsylvania State University, 1977."},{"key":"50_CR19","volume-title":"Knapsack Problems","author":"S. Martello","year":"1990","unstructured":"S. Martello and P. Toth. Knapsack Problems. John Wiley and Sons, Chichester, 1990."},{"key":"50_CR20","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/BFb0029570","volume-title":"On-Line Scheduling","author":"J. Sgall","year":"1998","unstructured":"J. Sgall. On-Line Scheduling. In A. Fiat and G. J. Woeginger, editors, Online Algorithms: The State of the Art, volume 1442 of LNCS, pages 196\u2013231. Springer-Verlag, 1998."},{"key":"50_CR21","unstructured":"A. C. Yao. Towards a Unified Measure of Complexity. Proc. 12th ACM Symposium on Theory of Computing, pages 222\u2013227, 1980."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45655-4_50","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T09:35:54Z","timestamp":1558258554000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45655-4_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540439967","9783540456551"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-45655-4_50","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]},"assertion":[{"value":"29 August 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}