{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T03:50:14Z","timestamp":1754020214058},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,8,19]],"date-time":"2012-08-19T00:00:00Z","timestamp":1345334400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cent Eur J Oper Res"],"published-print":{"date-parts":[[2013,12]]},"DOI":"10.1007\/s10100-012-0266-3","type":"journal-article","created":{"date-parts":[[2012,8,18]],"date-time":"2012-08-18T05:55:44Z","timestamp":1345269344000},"page":"685-698","source":"Crossref","is-referenced-by-count":11,"title":["Semi-on-line bin packing: a short overview and a new lower bound"],"prefix":"10.1007","volume":"21","author":[{"given":"J\u00e1nos","family":"Balogh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00f3zsef","family":"B\u00e9k\u00e9si","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,8,19]]},"reference":[{"key":"266_CR1","unstructured":"Balogh J, B\u00e9k\u00e9si J (2012) An Improved Lower Bound for a Semi-on-line Bin Packing Problem. In: Fourth International Workshop on Bin Packing and Placement Constraints (BPPC\u201912), Nantes, France"},{"key":"266_CR2","unstructured":"Balogh J, B\u00e9k\u00e9si J (2010) Semi-on-line bin packing: an overview and an improved lower bound. In: Proceedings of the (2010) mini-conference on applied theoretical computer science (MATCOS-10), pp 69\u201374. Koper, Slovenia"},{"key":"266_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2012.04.017","volume":"440\u2013441","author":"J Balogh","year":"2012","unstructured":"Balogh J, B\u00e9k\u00e9si J, Galambos G (2012) New lower bounds for certain bin packing algorithms. Theor Comput Sci 440\u2013441:1\u201313","journal-title":"Theor Comput Sci"},{"key":"266_CR4","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/s00607-008-0023-6","volume":"84","author":"J Balogh","year":"2009","unstructured":"Balogh J, B\u00e9k\u00e9si J, Galambos G, Mark\u00f3t MC (2009) Improved lower bounds for semi-on-line bin packing problems. Computing 84:139\u2013148","journal-title":"Computing"},{"key":"266_CR5","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1137\/050647049","volume":"38","author":"J Balogh","year":"2008","unstructured":"Balogh J, B\u00e9k\u00e9si J, Galambos G, Reinelt G (2008) Lower bound for bin packing problem with restricted repacking. SIAM J Comput 38:398\u2013410","journal-title":"SIAM J Comput"},{"key":"266_CR6","unstructured":"Balogh J, B\u00e9k\u00e9si J, Galambos G , Reinelt G (2010) On a multidimensional semi-online bin packing problem. In: Proceedings of the 8th international conference on applied informatics, vol. 2, pp 191\u2013197"},{"key":"266_CR7","doi-asserted-by":"crossref","unstructured":"Balogh J, B\u00e9k\u00e9si J, Galambos G, Reinelt G (2012) On-line bin packing with restricted repacking. J Comb Optim. doi: 10.1007\/s10878-012-9489-4","DOI":"10.1007\/s10878-012-9489-4"},{"key":"266_CR8","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1016\/j.tcs.2008.09.028","volume":"409","author":"JW-T Chan","year":"2008","unstructured":"Chan JW-T, Lam T-W, Wong PWH (2008) Dynamic bin packing of unit fractions items. Theor Comput Sci 409:521\u2013529","journal-title":"Theor Comput Sci"},{"key":"266_CR9","doi-asserted-by":"crossref","unstructured":"Coffman EG, Galambos G, Martello S, Vigo D (1999) Bin packing approximation algorithms: combinatorial analysis. In: Handbook of combinatorial optimization supplement volume. Kluwer Academic Publishers","DOI":"10.1007\/978-1-4757-3023-4_3"},{"key":"266_CR10","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1137\/0212014","volume":"12","author":"EG Coffmann","year":"1983","unstructured":"Coffmann EG, Garey MR, Johnson DS (1983) Dynamic bin packing. SIAM J Comput 12:227\u2013260","journal-title":"SIAM J Comput"},{"key":"266_CR11","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0167-6377(89)90027-8","volume":"8","author":"D Coppersmith","year":"1989","unstructured":"Coppersmith D, Raghavan P (1989) Multidimensional on-line bin packing: algorithms and worst-case analysis. Oper Res Lett 8:17\u201320","journal-title":"Oper Res Lett"},{"key":"266_CR12","unstructured":"Csirik J, Galambos G, Tur\u00e1n G (1983) Some results on bin packing. In: Proceedings of EURO VI, Vienna"},{"key":"266_CR13","doi-asserted-by":"crossref","unstructured":"Csirik J, Woeginger GJ (1998) On-line packing and covering problems. In: On-line algorithms. Lecture Notes in Computer Science, vol. 1442, Berlin, pp 147\u2013177","DOI":"10.1007\/BFb0029568"},{"key":"266_CR14","doi-asserted-by":"crossref","unstructured":"D\u00f3sa G (2007) The tight bound of first fit decreasing bin-packing algorithm is $$FFD(I )<= 11\/9 (I) +6\/9$$ . In: Proceedings of ESCAPE, pp 1\u201311","DOI":"10.1007\/978-3-540-74450-4_1"},{"key":"266_CR15","doi-asserted-by":"crossref","first-page":"2785","DOI":"10.1016\/j.dam.2009.03.015","volume":"157","author":"L Epstein","year":"2009","unstructured":"Epstein L, Kleiman E (2009) Resource augmented semi-online bounded space bin packing. Discrete Appl Math 157:2785\u20132798","journal-title":"Discrete Appl Math"},{"key":"266_CR16","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s10107-007-0200-y","volume":"119","author":"L Epstein","year":"2009","unstructured":"Epstein L, Levin A (2009) A robust APTAS for the classical bin packing problem. Math Program 119:33\u201349","journal-title":"Math Program"},{"key":"266_CR17","doi-asserted-by":"crossref","first-page":"1270","DOI":"10.1137\/060666329","volume":"19","author":"L Epstein","year":"2008","unstructured":"Epstein L, Levin A (2008) On bin packing with conflicts. SIAM J Optim 19:1270\u20131298","journal-title":"SIAM J Optim"},{"key":"266_CR18","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1016\/j.jda.2010.07.002","volume":"8","author":"L Epstein","year":"2010","unstructured":"Epstein L, Levy M (2010) Dynamic multi-dimensional bin packing. J Discrete Algorithms 8:356\u2013372","journal-title":"J Discrete Algorithms"},{"key":"266_CR19","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W Fernandez de la Vega","year":"1981","unstructured":"Fernandez de la Vega W, Lueker GS (1981) Bin packing can be solved within $$1+\\varepsilon $$ in linear time. Combinatorica 1:349\u2013355","journal-title":"Combinatorica"},{"key":"266_CR20","unstructured":"Galambos G (1985) A new heurisic for the classical bin packing problem. Technical report 82. Institute f\u00fcr Mathematik, Augsburg"},{"key":"266_CR21","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF02246509","volume":"52","author":"G Galambos","year":"1994","unstructured":"Galambos G, van Vliet A (1994) Lower bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms. Computing 52:281\u2013297","journal-title":"Computing"},{"key":"266_CR22","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/BF02248693","volume":"49","author":"G Galambos","year":"1993","unstructured":"Galambos G, Woeginger GJ (1993) Repacking helps in bounded space on-line bin packing. Computing 49:329\u2013338","journal-title":"Computing"},{"key":"266_CR23","unstructured":"Gambosi G, Postiglione A, Talamo M (1990) New algorithms for on-line bin packing. In: Algorithms and complexity, Proceedings of the iirst Italian conference, World Scientific, Singapore, pp 44\u201359"},{"key":"266_CR24","doi-asserted-by":"crossref","first-page":"1532","DOI":"10.1137\/S0097539799180408","volume":"30","author":"G Gambosi","year":"2000","unstructured":"Gambosi G, Postiglione A, Talamo M (2000) Algorithms for the relaxed on-line bin-packing model. SIAM J Comput 30:1532\u20131551","journal-title":"SIAM J Comput"},{"key":"266_CR25","volume-title":"Computers and Intractability (A guide to the theory of NP-completeness)","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and Intractability (A guide to the theory of NP-completeness). W.H, Freeman and Company, San Francisco"},{"key":"266_CR26","unstructured":"Grove EF (1995) On-line bin packing with lookahead. In: Proceedings of SODA, pp 430\u2013436"},{"key":"266_CR27","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/j.disopt.2004.11.001","volume":"2","author":"G Gutin","year":"2005","unstructured":"Gutin G, Jensen T, Yeo A (2005) Batched bin packing. Discrete Optim 2:71\u201382","journal-title":"Discrete Optim"},{"key":"266_CR28","first-page":"72","volume":"1","author":"G Gutin","year":"2006","unstructured":"Gutin G, Jensen T, Yeo A (2006) Optimal on-line bin packing with two item sizes. Algorithmic Oper Res 1:72\u201378","journal-title":"Algorithmic Oper Res"},{"key":"266_CR29","doi-asserted-by":"crossref","first-page":"1049","DOI":"10.1016\/j.ipl.2010.09.002","volume":"110","author":"X Han","year":"2010","unstructured":"Han X, Peng C, Ye D, Zhang D, Lan Y (2010) Dynamic bin packing with unit fraction items revisited. Inf Process Lett 110:1049\u20131054","journal-title":"Inf Process Lett"},{"key":"266_CR30","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0190(96)00112-3","volume":"59","author":"Z Ivkovi\u010d","year":"1996","unstructured":"Ivkovi\u010d Z, Lloyd EL (1996) A fundamental restriction on fully dynamic maintenance of bin packing. Inf Process Lett 59:229\u2013232","journal-title":"Inf Process Lett"},{"key":"266_CR31","doi-asserted-by":"crossref","first-page":"574","DOI":"10.1137\/S0097539794276749","volume":"28","author":"Z Ivkovi\u010d","year":"1998","unstructured":"Ivkovi\u010d Z, Lloyd EL (1998) Fully dynamic algorithms for bin packing: being (mostly) myopic helps. SIAM J Comput 28:574\u2013611","journal-title":"SIAM J Comput"},{"key":"266_CR32","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/S0020-0190(97)00092-6","volume":"63","author":"Z Ivkovi\u010d","year":"1997","unstructured":"Ivkovi\u010d Z, Lloyd E (1997) Partially dynamic bin packing can be solved within $$1+\\varepsilon $$ in (amortized) polylogarithmic time. Inf Process Lett 63:45\u201350","journal-title":"Inf Process Lett"},{"key":"266_CR33","unstructured":"Johnson DS (1973) Near-optimal bin packing algorithms. PhD thesis. MIT, Cambridge"},{"key":"266_CR34","doi-asserted-by":"crossref","unstructured":"Karmarkar N, Karp R (1982) An efficient approximation scheme for the one-dimensional bin packing problem. In: Proceedings of the 23rd annual symposium on foundations of computer science (FOCS\u201982), pp 312\u2013320","DOI":"10.1109\/SFCS.1982.61"},{"key":"266_CR35","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1145\/3828.3833","volume":"32","author":"CC Lee","year":"1985","unstructured":"Lee CC, Lee DT (1985) A simple on-line bin packing algorithm. J ACM 32:562\u2013572","journal-title":"J ACM"},{"key":"266_CR36","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0196-6774(89)90031-X","volume":"10","author":"P Ramanan","year":"1989","unstructured":"Ramanan P, Brown DJ, Lee CC, Lee DT (1989) On-line bin packing in linear time. J Algorithms 10:305\u2013326","journal-title":"J Algorithms"},{"key":"266_CR37","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0166-218X(91)90087-D","volume":"34","author":"MB Richey","year":"1991","unstructured":"Richey MB (1991) Improved bounds for harmonic-based bin packing algorithms. Discrete Appl Math 34:203\u2013227","journal-title":"Discrete Appl Math"},{"key":"266_CR38","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1145\/585265.585269","volume":"49","author":"SS Seiden","year":"2002","unstructured":"Seiden SS (2002) On the on-line bin packing problem. J ACM 49:640\u2013671","journal-title":"J ACM"},{"key":"266_CR39","doi-asserted-by":"crossref","unstructured":"van Vliet A (1992) An improved lower bound for on-line bin packing algorithms. Inf Process Lett 43: 277\u2013284","DOI":"10.1016\/0020-0190(92)90223-I"}],"container-title":["Central European Journal of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-012-0266-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10100-012-0266-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-012-0266-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,2]],"date-time":"2019-07-02T23:28:09Z","timestamp":1562110089000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10100-012-0266-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,19]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["266"],"URL":"https:\/\/doi.org\/10.1007\/s10100-012-0266-3","relation":{},"ISSN":["1435-246X","1613-9178"],"issn-type":[{"value":"1435-246X","type":"print"},{"value":"1613-9178","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,19]]}}}