{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T06:25:21Z","timestamp":1743143121329,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030394783"},{"type":"electronic","value":"9783030394790"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"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":[[2020]]},"DOI":"10.1007\/978-3-030-39479-0_4","type":"book-chapter","created":{"date-parts":[[2020,1,24]],"date-time":"2020-01-24T20:03:47Z","timestamp":1579896227000},"page":"43-59","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Robust Online Algorithms for Certain Dynamic Packing Problems"],"prefix":"10.1007","author":[{"given":"Sebastian","family":"Berndt","sequence":"first","affiliation":[]},{"given":"Valentin","family":"Dreismann","sequence":"additional","affiliation":[]},{"given":"Kilian","family":"Grage","sequence":"additional","affiliation":[]},{"given":"Klaus","family":"Jansen","sequence":"additional","affiliation":[]},{"given":"Ingmar","family":"Knof","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,1,25]]},"reference":[{"issue":"3","key":"4_CR1","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1137\/0212033","volume":"12","author":"BS Baker","year":"1983","unstructured":"Baker, B.S., Schwarz, J.S.: Shelf algorithms for two-dimensional packing problems. SIAM J. Comput. 12(3), 508\u2013525 (1983)","journal-title":"SIAM J. Comput."},{"key":"4_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/978-3-319-89441-6_9","volume-title":"Approximation and Online Algorithms","author":"J Balogh","year":"2018","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., D\u00f3sa, G., Epstein, L., Levin, A.: Lower bounds for several online variants of bin packing. In: Solis-Oba, R., Fleischer, R. (eds.) WAOA 2017. LNCS, vol. 10787, pp. 102\u2013117. Springer, Cham (2018). \nhttps:\/\/doi.org\/10.1007\/978-3-319-89441-6_9"},{"key":"4_CR3","doi-asserted-by":"publisher","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.: New lower bounds for certain classes of bin packing algorithms. Theoret. Comput. Sci. 440\u2013441, 1\u201313 (2012). \nhttps:\/\/doi.org\/10.1016\/j.tcs.2012.04.017\n\n. \nhttp:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304397512003611","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"4_CR4","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1287\/moor.1050.0168","volume":"31","author":"N Bansal","year":"2006","unstructured":"Bansal, N., Correa, J.R., Kenyon, C., Sviridenko, M.: Bin packing in multiple dimensions: inapproximability results and approximation schemes. Math. Oper. Res. 31(1), 31\u201349 (2006)","journal-title":"Math. Oper. Res."},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N., Eli\u00e1s, M., Khan, A.: Improved approximation for vector bin packing. In: Proceedings of SODA, pp. 1561\u20131579 (2016)","DOI":"10.1137\/1.9781611974331.ch106"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Bansal, N., Khan, A.: Improved approximation algorithm for two-dimensional bin packing. In: Proceedings of SODA, pp. 13\u201325 (2014)","DOI":"10.1137\/1.9781611973402.2"},{"key":"4_CR7","unstructured":"Berndt, S., Epstein, L., Jansen, K., Levin, A., Maack, M., Rohwedder, L.: Online bin covering with limited migration. In: Proceedings of ESA (2019, Accepted)"},{"key":"4_CR8","unstructured":"Berndt, S., Jansen, K., Klein, K.-M.: Fully dynamic bin packing revisited. In: Proceedings of APPROX-RANDOM, pp. 135\u2013151 (2015)"},{"key":"4_CR9","unstructured":"Blitz, D., Heydrich, S., van Stee, R., van Vliet, A., Woeginger, G.J.: Improved lower bounds for online hypercube and rectangle packing. CoRR, abs\/1607.01229 (2016)"},{"key":"4_CR10","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.cosrev.2016.12.001","volume":"24","author":"HI Christensen","year":"2017","unstructured":"Christensen, H.I., Khan, A., Pokutta, S., Tetali, P.: Approximation and online algorithms for multidimensional bin packing: a survey. Comput. Sci. Rev. 24, 63\u201379 (2017)","journal-title":"Comput. Sci. Rev."},{"issue":"1","key":"4_CR11","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0167-6377(89)90027-8","volume":"8","author":"D Coppersmith","year":"1989","unstructured":"Coppersmith, D., Raghavan, P.: Multidimensional on-line bin packing: algorithms and worst-case analysis. Oper. Res. Lett. 8(1), 17\u201320 (1989)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"4_CR12","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0020-0190(97)00120-8","volume":"63","author":"J Csirik","year":"1997","unstructured":"Csirik, J., Woeginger, G.J.: Shelf algorithms for on-line strip packing. Inf. Process. Lett. 63(4), 171\u2013175 (1997)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"4_CR13","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s10107-007-0200-y","volume":"119","author":"L Epstein","year":"2009","unstructured":"Epstein, L., Levin, A.: A robust APTAS for the classical bin packing problem. Math. Program. 119(1), 33\u201349 (2009)","journal-title":"Math. Program."},{"issue":"2","key":"4_CR14","doi-asserted-by":"publisher","first-page":"1310","DOI":"10.1137\/11082782X","volume":"23","author":"L Epstein","year":"2013","unstructured":"Epstein, L., Levin, A.: Robust approximation schemes for cube packing. SIAM J. Optim. 23(2), 1310\u20131343 (2013)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"4_CR15","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/s00453-012-9718-3","volume":"69","author":"L Epstein","year":"2014","unstructured":"Epstein, L., Levin, A.: Robust algorithms for preemptive scheduling. Algorithmica 69(1), 26\u201357 (2014)","journal-title":"Algorithmica"},{"key":"4_CR16","unstructured":"Feldkord, B., et al.: Fully-dynamic bin packing with little repacking. In: Proceedings of ICALP, pp. 51:1\u201351:24 (2018)"},{"key":"4_CR17","unstructured":"G\u00e1lvez, W., Soto, J.A., Verschae, J.: Symmetry exploitation for online machine covering with bounded migration. In: Proceedings of ESA, pp. 32:1\u201332:14 (2018)"},{"key":"4_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/978-3-642-39206-1_50","volume-title":"Automata, Languages, and Programming","author":"K Jansen","year":"2013","unstructured":"Jansen, K., Klein, K.-M.: A robust AFPTAS for online bin packing with polynomial migration. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7965, pp. 589\u2013600. Springer, Heidelberg (2013). \nhttps:\/\/doi.org\/10.1007\/978-3-642-39206-1_50"},{"key":"4_CR19","unstructured":"Jansen, K., Klein, K.-M., Kosche, M., Ladewig, L.: Online strip packing with polynomial migration. In: Proceedings of APPROX-RANDOM, pp. 13:1\u201313:18 (2017)"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"Jansen, K., van Stee, R.: On strip packing with rotations. In: Proceedings of STOC, pp. 755\u2013761 (2005)","DOI":"10.1145\/1060590.1060702"},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: Proceedings of FOCS, pp. 312\u2013320 (1982)","DOI":"10.1109\/SFCS.1982.61"},{"issue":"4","key":"4_CR22","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1287\/moor.25.4.645.12118","volume":"25","author":"C Kenyon","year":"2000","unstructured":"Kenyon, C., R\u00e9mila, E.: A near-optimal solution to a two-dimensional cutting stock problem. Math. Oper. Res. 25(4), 645\u2013656 (2000)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"4_CR23","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1287\/moor.1090.0381","volume":"34","author":"P Sanders","year":"2009","unstructured":"Sanders, P., Sivadasan, N., Skutella, M.: Online scheduling with bounded migration. Math. Oper. Res. 34(2), 481\u2013498 (2009)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"4_CR24","doi-asserted-by":"publisher","first-page":"991","DOI":"10.1287\/moor.2015.0765","volume":"41","author":"M Skutella","year":"2016","unstructured":"Skutella, M., Verschae, J.: Robust polynomial-time approximation schemes for parallel machine scheduling with job arrivals and departures. Math. Oper. Res. 41(3), 991\u20131021 (2016)","journal-title":"Math. Oper. Res."},{"key":"4_CR25","unstructured":"Van Vliet, A.: Lower and upper bounds for on-line bin packing and scheduling heuristics: Onder-en Bovengrenzen Voor On-line Bin Packing en Scheduling Heuristieken. Ph.D. thesis (1995)"},{"issue":"5","key":"4_CR26","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0020-0190(92)90223-I","volume":"43","author":"A Vliet van","year":"1992","unstructured":"van Vliet, A.: An improved lower bound for on-line bin packing algorithms. Inf. Process. Lett. 43(5), 277\u2013284 (1992). \nhttps:\/\/doi.org\/10.1016\/0020-0190(92)90223-I\n\n. \nhttp:\/\/www.sciencedirect.com\/science\/article\/pii\/002001909290223I","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"4_CR27","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(2), 207\u2013227 (1980)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-39479-0_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T08:04:14Z","timestamp":1583741054000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-39479-0_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030394783","9783030394790"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-39479-0_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"25 January 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Munich","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 September 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 September 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo2019.ak.in.tum.de\/index.php\/menue-waoa\/waoa-overview","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}