Skip to main content
Top

2020 | OriginalPaper | Chapter

Streaming Algorithms for Bin Packing and Vector Scheduling

Authors : Graham Cormode, Pavel Veselý

Published in: Approximation and Online Algorithms

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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, we provide a streaming asymptotic \(1+\varepsilon \)-approximation with \(\widetilde{\mathcal {O}}\left( \frac{1}{\varepsilon }\right) \) memory, where \(\widetilde{\mathcal {O}}\) hides logarithmic factors. Moreover, such a space bound is essentially optimal. Our algorithm implies a streaming \(d+\varepsilon \)-approximation for Vector Bin Packing in d dimensions, running in space \(\widetilde{\mathcal {O}}\left( \frac{d}{\varepsilon }\right) \). For the related Vector Scheduling problem, we show how to construct an input summary in space \(\widetilde{\mathcal {O}}(d^2\cdot m / \varepsilon ^2)\) that preserves the optimum value up to a factor of \(2 - \frac{1}{m} +\varepsilon \), where m is the number of identical machines.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Footnotes
1
We remark that some online algorithms can be implemented in the streaming model, as described in Sect. 2.1, but they give worse approximation guarantees.
 
2
Unlike for Bin Packing, an additive constant or even an additive \(o(\textsf {OPT})\) term does not help in the definition of the approximation ratio, since we can scale every number on input by any \(\alpha > 0\) and \(\textsf {OPT} \) scales by \(\alpha \) as well.
 
3
Note that if s appears more times in the stream, its rank is an interval rather than a single number. Also, unlike in [25], we order numbers non-increasingly, which is more convenient for Bin Packing.
 
4
More precisely, valid lower and upper bounds on the rank of \(s_i\) can be computed easily from the set of tuples.
 
Literature
2.
go back to reference 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–15 (2003) 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–15 (2003)
3.
go back to reference 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–970. ACM (2013) 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–970. ACM (2013)
4.
go back to reference 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–991. SIAM (2018)CrossRef 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–991. SIAM (2018)CrossRef
5.
go back to reference Balogh, J., Békési, J., Dósa, 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–5:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018) Balogh, J., Békési, J., Dósa, 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–5:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)
6.
go back to reference Balogh, J., Békési, J., Galambos, G.: New lower bounds for certain classes of bin packing algorithms. Theoret. Comput. Sci. 440–441, 1–13 (2012)MathSciNetCrossRef Balogh, J., Békési, J., Galambos, G.: New lower bounds for certain classes of bin packing algorithms. Theoret. Comput. Sci. 440–441, 1–13 (2012)MathSciNetCrossRef
7.
go back to reference Bansal, N., Eliáš, 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–1579. SIAM (2016) Bansal, N., Eliáš, 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–1579. SIAM (2016)
8.
go back to reference Bansal, N., Oosterwijk, T., Vredeveld, T., van der Zwaan, R.: Approximating vector scheduling: almost matching upper and lower bounds. Algorithmica 76(4), 1077–1096 (2016)MathSciNetCrossRef Bansal, N., Oosterwijk, T., Vredeveld, T., van der Zwaan, R.: Approximating vector scheduling: almost matching upper and lower bounds. Algorithmica 76(4), 1077–1096 (2016)MathSciNetCrossRef
9.
go back to reference Batu, T., Berenbrink, P., Sohler, C.: A sublinear-time approximation scheme for bin packing. Theoret. Comput. Sci. 410(47–49), 5082–5092 (2009)MathSciNetCrossRef Batu, T., Berenbrink, P., Sohler, C.: A sublinear-time approximation scheme for bin packing. Theoret. Comput. Sci. 410(47–49), 5082–5092 (2009)MathSciNetCrossRef
12.
go back to reference 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–668. SIAM (2014) 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–668. SIAM (2014)
13.
go back to reference Christensen, H.I., Khan, A., Pokutta, S., Tetali, P.: Approximation and online algorithms for multidimensional bin packing: a survey. Comput. Sci. Rev. 24, 63–79 (2017)MathSciNetCrossRef Christensen, H.I., Khan, A., Pokutta, S., Tetali, P.: Approximation and online algorithms for multidimensional bin packing: a survey. Comput. Sci. Rev. 24, 63–79 (2017)MathSciNetCrossRef
15.
16.
go back to reference Dósa, 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–549. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2013) Dósa, 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–549. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2013)
17.
go back to reference Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within 1 + \(\varepsilon \) in linear time. Combinatorica 1(4), 349–355 (1981)MathSciNetCrossRef Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within 1 + \(\varepsilon \) in linear time. Combinatorica 1(4), 349–355 (1981)MathSciNetCrossRef
19.
go back to reference 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–298 (1976)MathSciNetCrossRef 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–298 (1976)MathSciNetCrossRef
20.
go back to reference Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Freeman, New York (1979) Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Freeman, New York (1979)
21.
go back to reference Gilmore, P.C., Gomory, R.E.: A linear programming approach to the cutting-stock problem. Oper. Res. 9(6), 849–859 (1961)MathSciNetCrossRef Gilmore, P.C., Gomory, R.E.: A linear programming approach to the cutting-stock problem. Oper. Res. 9(6), 849–859 (1961)MathSciNetCrossRef
22.
go back to reference Gilmore, P.C., Gomory, R.E.: A linear programming approach to the cutting stock problem–part II. Oper. Res. 11(6), 863–888 (1963)CrossRef Gilmore, P.C., Gomory, R.E.: A linear programming approach to the cutting stock problem–part II. Oper. Res. 11(6), 863–888 (1963)CrossRef
23.
go back to reference Goemans, M.X., Rothvoß, 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–839. SIAM (2014) Goemans, M.X., Rothvoß, 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–839. SIAM (2014)
24.
go back to reference 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–565. SIAM (2000) 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–565. SIAM (2000)
25.
go back to reference 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–66, November 2001 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–66, November 2001
26.
go back to reference 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–478, October 2013 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–478, October 2013
27.
go back to reference 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–2625. SIAM (2017) 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–2625. SIAM (2017)
28.
go back to reference Rudin III, J.F.: Improved bounds for the on-line scheduling problem. Ph.D. thesis, The University of Texas at Dallas (2001) Rudin III, J.F.: Improved bounds for the on-line scheduling problem. Ph.D. thesis, The University of Texas at Dallas (2001)
29.
go back to reference Im, S., Kell, N., Kulkarni, J., Panigrahi, D.: Tight bounds for online vector scheduling. SIAM J. Comput. 48(1), 93–121 (2019)MathSciNetCrossRef Im, S., Kell, N., Kulkarni, J., Panigrahi, D.: Tight bounds for online vector scheduling. SIAM J. Comput. 48(1), 93–121 (2019)MathSciNetCrossRef
30.
go back to reference 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–72:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016) 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–72:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016)
32.
go back to reference 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–320, November 1982 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–320, November 1982
33.
go back to reference 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–78, October 2016 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–78, October 2016
35.
go back to reference Ge Luo, L., Wang, K.Y., Cormode, G.: Quantiles over data streams: experimental comparisons, new analyses, and further improvements. VLDB J. 25(4), 449–472 (2016)CrossRef Ge Luo, L., Wang, K.Y., Cormode, G.: Quantiles over data streams: experimental comparisons, new analyses, and further improvements. VLDB J. 25(4), 449–472 (2016)CrossRef
36.
go back to reference McGregor, A.: Graph stream algorithms: a survey. SIGMOD Rec. 43(1), 9–20 (2014)CrossRef McGregor, A.: Graph stream algorithms: a survey. SIGMOD Rec. 43(1), 9–20 (2014)CrossRef
37.
go back to reference Muthukrishnan, S.: Data streams: algorithms and applications. Found. Trends® Theoret. Comput. Sci. 1(2), 117–236 (2005) Muthukrishnan, S.: Data streams: algorithms and applications. Found. Trends® Theoret. Comput. Sci. 1(2), 117–236 (2005)
38.
go back to reference 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–249. ACM (2004) 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–249. ACM (2004)
39.
go back to reference Woeginger, G.J.: There is no asymptotic PTAS for two-dimensional vector packing. Inf. Process. Lett. 64(6), 293–297 (1997)MathSciNetCrossRef Woeginger, G.J.: There is no asymptotic PTAS for two-dimensional vector packing. Inf. Process. Lett. 64(6), 293–297 (1997)MathSciNetCrossRef
Metadata
Title
Streaming Algorithms for Bin Packing and Vector Scheduling
Authors
Graham Cormode
Pavel Veselý
Copyright Year
2020
DOI
https://doi.org/10.1007/978-3-030-39479-0_6

Premium Partner