{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T09:42:53Z","timestamp":1775122973508,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662439470","type":"print"},{"value":"9783662439487","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_36","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"429-441","source":"Crossref","is-referenced-by-count":32,"title":["Optimal Analysis of Best Fit Bin Packing"],"prefix":"10.1007","author":[{"given":"Gy\u00f6rgy","family":"D\u00f3sa","sequence":"first","affiliation":[]},{"given":"Ji\u0159\u00ed","family":"Sgall","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"36_CR1","doi-asserted-by":"publisher","first-page":"1914","DOI":"10.1016\/j.dam.2012.04.012","volume":"160","author":"J. Boyar","year":"2012","unstructured":"Boyar, J., D\u00f3sa, G., Epstein, L.: On the absolute approximation ratio for First Fit and related results. Discrete Appl. Math.\u00a0160, 1914\u20131923 (2012)","journal-title":"Discrete Appl. Math."},{"key":"36_CR2","unstructured":"Coffman, E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: A survey. In: Hochbaum, D. (ed.) Approximation algorithms. PWS Publishing Company (1997)"},{"key":"36_CR3","unstructured":"D\u00f3sa, G., Sgall, J.: First Fit bin packing: A tight analysis. In: Proc. of the 30th Ann. Symp. on Theor. Aspects of Comput. Sci (STACS). LIPIcs, vol.\u00a03, pp. 538\u2013549. Schloss Dagstuhl (2013)"},{"key":"36_CR4","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0097-3165(76)90001-7","volume":"21","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S., Yao, A.C.-C.: Resource constrained scheduling as generalized bin packing. J. Combin. Theory Ser. A\u00a021, 257\u2013298 (1976)","journal-title":"J. Combin. Theory Ser. A"},{"key":"36_CR5","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Graham, R.L., Ullman, J.D.: Worst-case analysis of memory allocation algorithms. In: Proc. 4th Symp. Theory of Computing (STOC), pp. 143\u2013150. ACM (1973)","DOI":"10.1145\/800152.804907"},{"key":"36_CR6","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R.L. Graham","year":"1966","unstructured":"Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell System Technical J.\u00a045, 1563\u20131581 (1966)","journal-title":"Bell System Technical J."},{"key":"36_CR7","first-page":"263","volume":"17","author":"R.L. Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math.\u00a017, 263\u2013269 (1969)","journal-title":"SIAM J. Appl. Math."},{"key":"36_CR8","unstructured":"Johnson, D.S.: Near-optimal bin packing algorithms. PhD thesis. MIT, Cambridge, MA (1973)"},{"key":"36_CR9","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1016\/S0022-0000(74)80026-7","volume":"8","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S.: Fast algorithms for bin packing. J. Comput. Syst. Sci.\u00a08, 272\u2013314 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"36_CR10","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1093\/comjnl\/3.4.256","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-dimensional packing algorithms. SIAM J. Comput.\u00a03, 256\u2013278 (1974)","journal-title":"SIAM J. Comput."},{"key":"36_CR11","unstructured":"N\u00e9meth, Z.: A first fit algoritmus abszol\u00fat hib\u00e1j\u00e1r\u00f3l (in Hungarian). E\u00f6tv\u00f6s Lor\u00e1nd Univ., Budapest, Hungary (2011)"},{"key":"36_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-642-30347-0_31","volume-title":"Fun with Algorithms","author":"J. Sgall","year":"2012","unstructured":"Sgall, J.: A new analysis of best fit bin packing. In: Kranakis, E., Krizanc, D., Luccio, F. (eds.) FUN 2012. LNCS, vol.\u00a07288, pp. 315\u2013321. Springer, Heidelberg (2012)"},{"key":"36_CR13","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1002\/1520-6750(199406)41:4<579::AID-NAV3220410409>3.0.CO;2-G","volume":"41","author":"D. Simchi-Levi","year":"1994","unstructured":"Simchi-Levi, D.: New worst case results for the bin-packing problem. Naval Research Logistics\u00a041, 579\u2013585 (1994)","journal-title":"Naval Research Logistics"},{"key":"36_CR14","unstructured":"Ullman, J.D.: The performance of a memory allocation algorithm. Technical Report 100, Princeton Univ., Princeton, NJ (1971)"},{"key":"36_CR15","doi-asserted-by":"crossref","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press (2011)","DOI":"10.1017\/CBO9780511921735"},{"key":"36_CR16","doi-asserted-by":"publisher","first-page":"1668","DOI":"10.1016\/j.dam.2010.05.026","volume":"158","author":"B. Xia","year":"2010","unstructured":"Xia, B., Tan, Z.: Tighter bounds of the First Fit algorithm for the bin-packing problem. Discrete Appl. Math.\u00a0158, 1668\u20131675 (2010)","journal-title":"Discrete Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T06:06:11Z","timestamp":1689314771000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}