{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T11:41:31Z","timestamp":1743075691718,"version":"3.40.3"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319126906"},{"type":"electronic","value":"9783319126913"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-12691-3_2","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T21:11:32Z","timestamp":1415999492000},"page":"13-24","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Asymptotic Competitive Scheme for Online Bin Packing"],"prefix":"10.1007","author":[{"given":"Lin","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Deshi","family":"Ye","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guochuan","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,11,13]]},"reference":[{"key":"2_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-642-18318-8_3","volume-title":"Approximation and Online Algorithms","author":"J Balogh","year":"2011","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., Galambos, G.: New lower bounds for certain classes of bin packing algorithms. In: Jansen, K., Solis-Oba, R. (eds.) WAOA 2010. LNCS, vol. 6534, pp. 25\u201336. Springer, Heidelberg (2011)"},{"key":"2_CR2","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.tcs.2006.06.001","volume":"362","author":"J Boyar","year":"2006","unstructured":"Boyar, J., Epstein, L., Favrholdt, L.M., et al.: The maximum resource bin packing problem. Theoret. Comput. Sci. 362, 127\u2013139 (2006)","journal-title":"Theoret. Comput. Sci."},{"key":"2_CR3","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/BF00264439","volume":"18","author":"D Brown","year":"1982","unstructured":"Brown, D., Baker, B.S., Katseff, H.P.: Lower bounds for on-line two-dimensional packing algorithms. Acta Informatica 18, 207\u2013225 (1982)","journal-title":"Acta Informatica"},{"key":"2_CR4","unstructured":"Chen, L., Ye, D., Zhang, G.: Approximating the optimal competitive ratio for an ancient online scheduling problem. CoRR, abs\/1302.3946v1 (2013)"},{"key":"2_CR5","unstructured":"Do\u015ba, G., Sgall, J.: First fit bin packing: A tight analysis. In: Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 538\u2013549 (2013)"},{"key":"2_CR6","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W Fernandez de La Vega","year":"1981","unstructured":"Fernandez de La Vega, W., Lueker, G.S.: Bin packing can be solved within 1+ $$\\varepsilon $$ in linear time. Combinatorica 1, 349\u2013355 (1981)","journal-title":"Combinatorica"},{"key":"2_CR7","volume-title":"Computers and Intractability: A Guide to the theory of of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the theory of of NP-Completeness. Freeman and Company, San Francisco (1979)"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"G\u00fcnther, E., Maurer, O., Megow, N., Wiese, A.: A new approach to online scheduling: Approximating the optimal competitive ratio. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 118\u2013128 (2013)","DOI":"10.1137\/1.9781611973105.9"},{"key":"2_CR9","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1137\/0203025","volume":"3","author":"DS 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-dimensional packing algorithms. SIAM J. Comput. 3, 256\u2013278 (1974)","journal-title":"SIAM J. Comput."},{"key":"2_CR10","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1016\/S0022-0000(74)80026-7","volume":"8","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Fast algorithms for bin packing. J. Comput. Syst. Sci. 8, 272\u2013314 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Karmarkar, N., Karp, R.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 312\u2013320 (1982)","DOI":"10.1109\/SFCS.1982.61"},{"key":"2_CR12","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1145\/3828.3833","volume":"32","author":"CC Lee","year":"1985","unstructured":"Lee, C.C., Lee, D.T.: A simple online bin packing algorithm. J. ACM 32, 562\u2013572 (1985)","journal-title":"J. ACM"},{"key":"2_CR13","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0196-6774(89)90031-X","volume":"10","author":"P Ramanan","year":"1989","unstructured":"Ramanan, P., Brown, D., Lee, C.C., Lee, D.T.: Online bin packing in linear time. J. Algorithms 10, 305\u2013326 (1989)","journal-title":"J. Algorithms"},{"key":"2_CR14","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1145\/585265.585269","volume":"49","author":"S Seiden","year":"2002","unstructured":"Seiden, S.: On the online bin packing problem. J. ACM 49, 640\u2013671 (2002)","journal-title":"J. ACM"},{"key":"2_CR15","unstructured":"Ullman, J.: The performance of a memory allocation algorithm. Technical report. Princeton University. Dept. of Electrical Engineering (1971)"},{"key":"2_CR16","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1145\/322186.322187","volume":"27","author":"ACC Yao","year":"1980","unstructured":"Yao, A.C.C.: New algorithms for bin packing. J. ACM 27, 207\u2013227 (1980)","journal-title":"J. ACM"},{"key":"2_CR17","doi-asserted-by":"crossref","unstructured":"Y. Zhang, F.Y.L. Chin, H.-F. Ting et al. Online algorithms for 1-space bounded 2-dimensional bin packing and square packing. Theortical Comput. Sci. (2014) (to appear)","DOI":"10.1016\/j.tcs.2014.02.045"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-12691-3_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T19:04:10Z","timestamp":1676660650000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-12691-3_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319126906","9783319126913"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-12691-3_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"13 November 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}