{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T02:43:31Z","timestamp":1743043411999,"version":"3.40.3"},"publisher-location":"Cham","reference-count":39,"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_6","type":"book-chapter","created":{"date-parts":[[2020,1,24]],"date-time":"2020-01-24T20:03:47Z","timestamp":1579896227000},"page":"72-88","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Streaming Algorithms for Bin Packing and Vector Scheduling"],"prefix":"10.1007","author":[{"given":"Graham","family":"Cormode","sequence":"first","affiliation":[]},{"given":"Pavel","family":"Vesel\u00fd","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,1,25]]},"reference":[{"issue":"2","key":"6_CR1","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1137\/S0097539797324874","volume":"29","author":"S Albers","year":"1999","unstructured":"Albers, S.: Better bounds for online scheduling. SIAM J. Comput. 29(2), 459\u2013473 (1999)","journal-title":"SIAM J. Comput."},{"key":"6_CR2","unstructured":"Applegate, D., Buriol, L.S., Dillard, B.L., Johnson, D.S., Shor, P.W.: The cutting-stock approach to bin packing: theory and experiments. In: ALENEX, vol. 3, pp. 1\u201315 (2003)"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Azar, Y., Cohen, I.R., Kamara, S., Shepherd, B.: Tight bounds for online vector bin packing. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 2013, pp. 961\u2013970. ACM (2013)","DOI":"10.1145\/2488608.2488730"},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"980","DOI":"10.1137\/1.9781611975031.63","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Yossi Azar","year":"2018","unstructured":"Azar, Y., Cohen, I.R., Panigrahi, D.: Randomized algorithms for online vector load balancing. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pp. 980\u2013991. SIAM (2018)"},{"key":"6_CR5","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., D\u00f3sa, G., Epstein, L., Levin, A.: A new and improved algorithm for online bin packing. In: 26th Annual European Symposium on Algorithms (ESA 2018), LIPIcs, vol. 112, pp. 5:1\u20135:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)"},{"key":"6_CR6","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)","journal-title":"Theoret. Comput. Sci."},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"Bansal, N., Eli\u00e1\u0161, M., Khan, A.: Improved approximation for vector bin packing. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pp. 1561\u20131579. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch106"},{"issue":"4","key":"6_CR8","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1007\/s00453-016-0116-0","volume":"76","author":"N Bansal","year":"2016","unstructured":"Bansal, N., Oosterwijk, T., Vredeveld, T., van der Zwaan, R.: Approximating vector scheduling: almost matching upper and lower bounds. Algorithmica 76(4), 1077\u20131096 (2016)","journal-title":"Algorithmica"},{"issue":"47\u201349","key":"6_CR9","doi-asserted-by":"publisher","first-page":"5082","DOI":"10.1016\/j.tcs.2009.08.006","volume":"410","author":"T Batu","year":"2009","unstructured":"Batu, T., Berenbrink, P., Sohler, C.: A sublinear-time approximation scheme for bin packing. Theoret. Comput. Sci. 410(47\u201349), 5082\u20135092 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"6_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-642-29700-7_16","volume-title":"Frontiers in Algorithmics and Algorithmic Aspects in Information and Management","author":"R Beigel","year":"2012","unstructured":"Beigel, R., Fu, B.: A dense hierarchy of sublinear time approximation schemes for bin packing. In: Snoeyink, J., Lu, P., Su, K., Wang, L. (eds.) AAIM\/FAW -2012. LNCS, vol. 7285, pp. 172\u2013181. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-29700-7_16"},{"issue":"4","key":"6_CR11","doi-asserted-by":"publisher","first-page":"837","DOI":"10.1137\/S0097539799356265","volume":"33","author":"C Chekuri","year":"2004","unstructured":"Chekuri, C., Khanna, S.: On multidimensional packing problems. SIAM J. Comput. 33(4), 837\u2013851 (2004)","journal-title":"SIAM J. Comput."},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Chen, L., Jansen, K., Zhang, G.: On the optimality of approximation schemes for the classical scheduling problem. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pp. 657\u2013668. SIAM (2014)","DOI":"10.1137\/1.9781611973402.50"},{"key":"6_CR13","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."},{"key":"6_CR14","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/978-1-4419-7997-1_35","volume-title":"Handbook of Combinatorial Optimization","author":"EG Coffman","year":"2013","unstructured":"Coffman, E.G., Csirik, J., Galambos, G., Martello, S., Vigo, D.: Bin packing approximation algorithms: survey and classification. In: Pardalos, P.M., Du, D.-Z., Graham, R.L. (eds.) Handbook of Combinatorial Optimization, pp. 455\u2013531. Springer, New York (2013). https:\/\/doi.org\/10.1007\/978-1-4419-7997-1_35"},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Cormode, G., Vesel\u00fd, P.: Tight lower bound for comparison-based quantile summaries. arXiv e-prints, page arXiv:1905.03838 , May 2019","DOI":"10.1145\/3375395.3387650"},{"key":"6_CR16","unstructured":"D\u00f3sa, G., Sgall, J.: First fit bin packing: a tight analysis. In: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), LIPIcs, vol. 20, pp. 538\u2013549. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2013)"},{"issue":"4","key":"6_CR17","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(4), 349\u2013355 (1981)","journal-title":"Combinatorica"},{"issue":"6","key":"6_CR18","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/1099-1425(200011\/12)3:6<343::AID-JOS54>3.0.CO;2-2","volume":"3","author":"R Fleischer","year":"2000","unstructured":"Fleischer, R., Wahl, M.: On-line scheduling revisited. J. Scheduling 3(6), 343\u2013353 (2000)","journal-title":"J. Scheduling"},{"issue":"3","key":"6_CR19","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0097-3165(76)90001-7","volume":"21","author":"MR 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. Comb. Theory Ser. A 21(3), 257\u2013298 (1976)","journal-title":"J. Comb. Theory Ser. A"},{"key":"6_CR20","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Freeman, New York (1979)"},{"issue":"6","key":"6_CR21","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1287\/opre.9.6.849","volume":"9","author":"PC Gilmore","year":"1961","unstructured":"Gilmore, P.C., Gomory, R.E.: A linear programming approach to the cutting-stock problem. Oper. Res. 9(6), 849\u2013859 (1961)","journal-title":"Oper. Res."},{"issue":"6","key":"6_CR22","doi-asserted-by":"publisher","first-page":"863","DOI":"10.1287\/opre.11.6.863","volume":"11","author":"PC Gilmore","year":"1963","unstructured":"Gilmore, P.C., Gomory, R.E.: A linear programming approach to the cutting stock problem\u2013part II. Oper. Res. 11(6), 863\u2013888 (1963)","journal-title":"Oper. Res."},{"key":"6_CR23","doi-asserted-by":"crossref","unstructured":"Goemans, M.X., Rothvo\u00df, T.: Polynomiality for bin packing with a constant number of item types. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pp. 830\u2013839. SIAM (2014)","DOI":"10.1137\/1.9781611973402.61"},{"key":"6_CR24","unstructured":"Gormley, T., Reingold, N., Torng, E., Westbrook, J.: Generating adversaries for request-answer games. In: Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms, SODA 2000, pp. 564\u2013565. SIAM (2000)"},{"key":"6_CR25","doi-asserted-by":"crossref","unstructured":"Greenwald, M., Khanna, S.: Space-efficient online computation of quantile summaries. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2001, pp. 58\u201366, November 2001","DOI":"10.1145\/376284.375670"},{"key":"6_CR26","doi-asserted-by":"crossref","unstructured":"Harris, D.G., Srinivasan, A.: The Moser-Tardos framework with partial resampling. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013, pp. 469\u2013478, October 2013","DOI":"10.1109\/FOCS.2013.57"},{"key":"6_CR27","doi-asserted-by":"crossref","unstructured":"Hoberg, R., Rothvoss, T.: A logarithmic additive integrality gap for bin packing. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pp. 2616\u20132625. SIAM (2017)","DOI":"10.1137\/1.9781611974782.172"},{"key":"6_CR28","unstructured":"Rudin III, J.F.: Improved bounds for the on-line scheduling problem. Ph.D. thesis, The University of Texas at Dallas (2001)"},{"issue":"1","key":"6_CR29","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1137\/17M111835X","volume":"48","author":"S Im","year":"2019","unstructured":"Im, S., Kell, N., Kulkarni, J., Panigrahi, D.: Tight bounds for online vector scheduling. SIAM J. Comput. 48(1), 93\u2013121 (2019)","journal-title":"SIAM J. Comput."},{"key":"6_CR30","unstructured":"Jansen, K., Klein, K.-M., Verschae, J.: Closing the gap for makespan scheduling via sparsification techniques. In: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), LIPIcs vol. 55, pp. 72:1\u201372:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016)"},{"key":"6_CR31","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":"6_CR32","doi-asserted-by":"crossref","unstructured":"Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: 23rd Annual Symposium on Foundations of Computer Science, SFCS 1982, pp. 312\u2013320, November 1982","DOI":"10.1109\/SFCS.1982.61"},{"key":"6_CR33","doi-asserted-by":"crossref","unstructured":"Karnin, Z., Lang, K., Liberty, E.: Optimal quantile approximation in streams. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 71\u201378, October 2016","DOI":"10.1109\/FOCS.2016.17"},{"key":"6_CR34","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 on-line bin-packing algorithm. J. ACM 32, 562\u2013572 (1985)","journal-title":"J. ACM"},{"issue":"4","key":"6_CR35","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/s00778-016-0424-7","volume":"25","author":"L Ge Luo","year":"2016","unstructured":"Ge Luo, L., Wang, K.Y., Cormode, G.: Quantiles over data streams: experimental comparisons, new analyses, and further improvements. VLDB J. 25(4), 449\u2013472 (2016)","journal-title":"VLDB J."},{"issue":"1","key":"6_CR36","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/2627692.2627694","volume":"43","author":"A McGregor","year":"2014","unstructured":"McGregor, A.: Graph stream algorithms: a survey. SIGMOD Rec. 43(1), 9\u201320 (2014)","journal-title":"SIGMOD Rec."},{"key":"6_CR37","unstructured":"Muthukrishnan, S.: Data streams: algorithms and applications. Found. Trends\u00ae Theoret. Comput. Sci. 1(2), 117\u2013236 (2005)"},{"key":"6_CR38","doi-asserted-by":"crossref","unstructured":"Shrivastava, N., Buragohain, C., Agrawal, D., Suri, S.: Medians and beyond: new aggregation techniques for sensor networks. In: Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, SenSys 2004, pp. 239\u2013249. ACM (2004)","DOI":"10.1145\/1031495.1031524"},{"issue":"6","key":"6_CR39","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/S0020-0190(97)00179-8","volume":"64","author":"GJ Woeginger","year":"1997","unstructured":"Woeginger, G.J.: There is no asymptotic PTAS for two-dimensional vector packing. Inf. Process. Lett. 64(6), 293\u2013297 (1997)","journal-title":"Inf. Process. Lett."}],"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_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,23]],"date-time":"2021-02-23T22:15:12Z","timestamp":1614118512000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-39479-0_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030394783","9783030394790"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-39479-0_6","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"}}]}}