## G. Cormode and P. Veselý.
Streaming algorithms for bin packing and vector scheduling.
*Theory of Computing Systems*, 65(6):916-942, 2021.

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

[ bib |
DOI |
.pdf ]
Back

*This file was generated by
bibtex2html 1.92.*