{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:34:45Z","timestamp":1759638885155,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2020,11,12]],"date-time":"2020-11-12T00:00:00Z","timestamp":1605139200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,11,12]],"date-time":"2020-11-12T00:00:00Z","timestamp":1605139200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["ERC-2014-CoG 647557"],"award-info":[{"award-number":["ERC-2014-CoG 647557"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2021,8]]},"abstract":"Abstract<\/jats:title>Problems involving the efficient arrangement of simple objects, as captured by bin packing and makespan scheduling, are fundamental tasks in combinatorial optimization. These are well understood in the traditional online and offline cases, but have been less well-studied when the volume of the input is truly massive, and cannot even be read into memory. This is captured by the streaming model of computation, where the aim is to approximate the cost of the solution in one pass over the data, using small space. As a result, streaming algorithms produce concise input summaries that approximately preserve the optimum value. We design the first efficient streaming algorithms for these fundamental problems in combinatorial optimization. For Bin Packing<\/jats:sc>, we provide a streaming asymptotic (1 + \u03b5<\/jats:italic>)-approximation with $\\widetilde {O}$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n <\/mml:mrow>\n ~<\/mml:mo>\n <\/mml:mover>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>$\\left (\\frac {1}{\\varepsilon }\\right )$<\/jats:tex-math>\n \n \n \n \n 1<\/mml:mn>\n <\/mml:mrow>\n \n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:mfenced>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where $\\widetilde {{{O}}}$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n <\/mml:mrow>\n ~<\/mml:mo>\n <\/mml:mover>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> hides logarithmic factors. Moreover, such a space bound is essentially optimal. Our algorithm implies a streaming (d<\/jats:italic> + \u03b5<\/jats:italic>)-approximation for Vector Bin Packing<\/jats:sc> in d<\/jats:italic> dimensions, running in space $\\widetilde {{{O}}}\\left (\\frac {d}{\\varepsilon }\\right )$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n <\/mml:mrow>\n ~<\/mml:mo>\n <\/mml:mover>\n \n \n \n \n d<\/mml:mi>\n <\/mml:mrow>\n \n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:mfenced>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. For the related Vector Scheduling<\/jats:sc> problem, we show how to construct an input summary in space $\\widetilde {{{O}}}(d^{2}\\cdot m \/ \\varepsilon ^{2})$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n <\/mml:mrow>\n ~<\/mml:mo>\n <\/mml:mover>\n (<\/mml:mo>\n \n \n d<\/mml:mi>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \u22c5<\/mml:mo>\n m<\/mml:mi>\n \/<\/mml:mo>\n \n \n \u03b5<\/mml:mi>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> that preserves the optimum value up to a factor of $2 - \\frac {1}{m} +\\varepsilon $<\/jats:tex-math>\n 2<\/mml:mn>\n \u2212<\/mml:mo>\n \n \n 1<\/mml:mn>\n <\/mml:mrow>\n \n m<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n +<\/mml:mo>\n \u03b5<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where m<\/jats:italic> is the number of identical machines.<\/jats:p>","DOI":"10.1007\/s00224-020-10011-y","type":"journal-article","created":{"date-parts":[[2020,11,12]],"date-time":"2020-11-12T11:03:06Z","timestamp":1605178986000},"page":"916-942","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Streaming Algorithms for Bin Packing and Vector Scheduling"],"prefix":"10.1007","volume":"65","author":[{"given":"Graham","family":"Cormode","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1169-7934","authenticated-orcid":false,"given":"Pavel","family":"Vesel\u00fd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,12]]},"reference":[{"issue":"2","key":"10011_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":"10011_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":"10011_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 \u201913 ACM, pp 961\u2013970 (2013)","DOI":"10.1145\/2488608.2488730"},{"key":"10011_CR4","doi-asserted-by":"crossref","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 \u201918 SIAM, pp 980\u2013991 (2018)","DOI":"10.1137\/1.9781611975031.63"},{"key":"10011_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), of LIPIcs. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, vol. 112 , pp 5:1\u20135:14 (2018)"},{"key":"10011_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2012.04.017","volume":"440-441","author":"J Balogh","year":"2012","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., Galambos, G.: New lower bounds for certain classes of bin packing algorithms. Theor. Comput. Sci. 440-441, 1\u201313 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"10011_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 \u201916 SIAM, pp 1561\u20131579 (2016)","DOI":"10.1137\/1.9781611974331.ch106"},{"issue":"4","key":"10011_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-49","key":"10011_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. Theor. Comput. Sci. 410(47-49), 5082\u20135092 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"10011_CR10","doi-asserted-by":"crossref","unstructured":"Beigel, R., Fu, B.: A dense hierarchy of sublinear time approximation schemes for bin packing. In: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, pp 172\u2013181. Springer, New York (2012)","DOI":"10.1007\/978-3-642-29700-7_16"},{"issue":"4","key":"10011_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":"10011_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 \u201914 SIAM, pp 657\u2013668 (2014)","DOI":"10.1137\/1.9781611973402.50"},{"key":"10011_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":"10011_CR14","doi-asserted-by":"crossref","unstructured":"Coffman, E.G. Jr, Csirik, J., Galambos, G., Martello, S., Vigo, D.: Bin packing approximation algorithms: survey and classification. In: Handbook of Combinatorial Optimization, pp 455\u2013531. Springer, New York (2013)","DOI":"10.1007\/978-1-4419-7997-1_35"},{"key":"10011_CR15","doi-asserted-by":"crossref","unstructured":"Cormode, G., Vesel\u00fd, P.: Streaming algorithms for bin packing and vector scheduling. In: Bampis, E., Megow, N. (eds.) Approximation and Online Algorithms, pp 72\u201388. Springer International Publishing, Cham (2020)","DOI":"10.1007\/s00224-020-10011-y"},{"key":"10011_CR16","doi-asserted-by":"crossref","unstructured":"Cormode, G., Vesel\u00fd, P.: A tight lower bound for comparison-based quantile summaries. In: Proceedings of the 39th ACM SIGMOD- SIGACT-SIGAI Symposium on Principles of Database Systems, PODS\u201920, New York, NY, USA. ACM, pp 81\u201393 (2020)","DOI":"10.1145\/3375395.3387650"},{"key":"10011_CR17","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), vol. 20 of LIPIcs. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, pp 538\u2013549 (2013)"},{"key":"10011_CR18","unstructured":"Feldkord, B., Feldotto, M., Gupta, A., Guruganesh, G., Kumar, A., Riechers, S., Wajc, D.: Fully-dynamic bin packing with little repacking. In: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), vol. 107 of LIPIcs. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, pp 51:1\u201351:24 (2018)"},{"issue":"4","key":"10011_CR19","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 + \u03b5 in linear time. Combinatorica 1(4), 349\u2013355 (1981)","journal-title":"Combinatorica"},{"issue":"6","key":"10011_CR20","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. Sched. 3(6), 343\u2013353 (2000)","journal-title":"J. Sched."},{"issue":"3","key":"10011_CR21","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. Combinat. Theory Series A 21(3), 257\u2013298 (1976)","journal-title":"J. Combinat. Theory Series A"},{"key":"10011_CR22","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. Freeman (1979)"},{"issue":"6","key":"10011_CR23","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":"10011_CR24","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\u2014part ii. Oper. Res. 11(6), 863\u2013888 (1963)","journal-title":"Oper. Res."},{"key":"10011_CR25","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 \u201914. SIAM, pp 830\u2013839 (2014)","DOI":"10.1137\/1.9781611973402.61"},{"key":"10011_CR26","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 \u201900 SIAM, pp 564\u2013565 (2000)"},{"key":"10011_CR27","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 \u201901, pp 58\u201366 (2001)","DOI":"10.1145\/376284.375670"},{"key":"10011_CR28","doi-asserted-by":"crossref","unstructured":"Harris, D.G., Srinivasan, A.: The Moser-Tardos framework with partial resampling. In: IEEE 54th Annual Symposium on Foundations of Computer Science FOCS \u201913, pp 469\u2013478 (2013)","DOI":"10.1109\/FOCS.2013.57"},{"key":"10011_CR29","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 \u201917 SIAM, pp 2616\u20132625 (2017)","DOI":"10.1137\/1.9781611974782.172"},{"key":"10011_CR30","unstructured":"Rudin, F. IIIJ: Improved bounds for the on-line scheduling problem. PhD thesis, The University of Texas at Dallas (2001)"},{"issue":"1","key":"10011_CR31","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":"10011_CR32","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), vo. 55 of LIPIcs. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, pp 72:1\u201372:13 (2016)"},{"key":"10011_CR33","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":"10011_CR34","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 \u201982, pp 312\u2013320 (1982)","DOI":"10.1109\/SFCS.1982.61"},{"key":"10011_CR35","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 (2016)","DOI":"10.1109\/FOCS.2016.17"},{"key":"10011_CR36","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":"10011_CR37","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/s00778-016-0424-7","volume":"25","author":"G Luo","year":"2016","unstructured":"Luo, G., Wang, L., Yi, K., 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":"10011_CR38","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."},{"issue":"2","key":"10011_CR39","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1561\/0400000002","volume":"1","author":"S Muthukrishnan","year":"2005","unstructured":"Muthukrishnan, S: Data streams: algorithms and applications. Foundat Trends\u00ae; Theoret Comput Sci 1(2), 117\u2013236 (2005)","journal-title":"Foundat Trends\u00ae; Theoret Comput Sci"},{"key":"10011_CR40","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 \u201904 ACM, pp 239\u2013249 (2004)","DOI":"10.1145\/1031495.1031524"},{"issue":"6","key":"10011_CR41","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":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10011-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-020-10011-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10011-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,7]],"date-time":"2021-08-07T22:03:08Z","timestamp":1628373788000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-020-10011-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,12]]},"references-count":41,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["10011"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-10011-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2020,11,12]]},"assertion":[{"value":"27 September 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 November 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}