Abstract
This paper introduces the first efficient streaming algorithms for fundamental combinatorial optimization problems: Bin Packing and Vector Scheduling. By adapting quantile summaries—data structures typically used for statistical estimation—the authors demonstrate how to approximate optimal solutions for massive datasets using only a tiny fraction of the memory. The proposed algorithms achieve near-optimal space complexity for $(1+\epsilon)$-approximations in the streaming model.
Introduction
In the classic Bin Packing problem, a set of items must be packed into the minimum number of unit-capacity bins. Vector Scheduling extends this to multi-dimensional tasks (e.g., jobs requiring specific CPU, RAM, and bandwidth) that must be assigned to machines to minimize the maximum load, or "makespan."
While these problems are well-understood in offline and online settings, the streaming model presents unique challenges. In a stream, data is too massive to fit in memory, and it can only be processed in a single pass. The goal is to maintain a "concise summary" that is small enough to store but accurate enough to estimate the optimal solution once the stream concludes.
Methodology
Quantile Summaries for Bin Packing
The core innovation for Bin Packing involves leveraging the connection between item distributions and approximation schemes. The authors use the Greenwald-Khanna algorithm to maintain a quantile summary of item sizes. This summary allows for "linear" or "geometric" grouping, where item sizes are rounded so that many distinct items can be treated as identical "types." This drastically reduces the complexity of the problem while maintaining a $(1+\epsilon)$ approximation ratio.
Containerization for Vector Scheduling
For Vector Scheduling, the authors introduce a novel "container" approach. Instead of storing every small job, the algorithm aggregates them into vector containers until they reach a specific size threshold. Large jobs are stored explicitly, while small jobs are summarized by these containers, effectively balancing accuracy and space.
Theoretical Reductions
The paper provides a formal reduction showing that the space complexity of Bin Packing is fundamentally tied to the "Estimating Rank" problem in streaming. This proves that their space bounds are near-optimal for any algorithm that accesses item sizes via comparisons.
Key Results
The theoretical analysis yields several significant bounds:
- Bin Packing: An asymptotic $1 + \epsilon$-approximation using only $\tilde{O}(\frac{1}{\epsilon} \log \text{OPT})$ memory. This constitutes a Polynomial-Time Approximation Scheme (PTAS) in a streaming setting.
- Vector Bin Packing: A $d + \epsilon$-approximation in $O(\frac{d}{\epsilon} \log \frac{d}{\epsilon} \log \text{OPT})$ space.
- Vector Scheduling: A $(2 - \frac{1}{m} + \epsilon)$-approximation for $m$ machines in $O(d^2 \cdot m / \epsilon^2)$ space.
Discussion and Future Work
Unlike online algorithms, which must place items immediately, streaming algorithms can wait until the end of the stream to "solve" the problem using their internal summary. This flexibility allows for much better approximation ratios than the best possible online algorithms.
However, challenges remain. While the space used during the stream is small, calculating the final answer from the summary can be computationally expensive (NP-hard in some cases). Additionally, providing the actual assignment (which item goes where) for a massive stream is difficult because the algorithm cannot store all item IDs. Future research may explore whether $(1 + \epsilon)$ approximations for Vector Bin Packing can be achieved without space complexity that scales exponentially with the number of dimensions $d$.
Summary updated