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 @math -approximation with @math memory, where @math hides logarithmic factors. Moreover, such a space bound is essentially optimal. Our algorithm implies a streaming @math -approximation for Vector Bin Packing in @math dimensions, running in space @math . For the related Vector Scheduling problem, we show how to construct an input summary in space @math that preserves the optimum value up to a factor of @math , where @math is the number of identical machines.
The bin packing problem is defined as follows: given a set of n items with sizes 00, we present an algorithm A"@e that has sampling access to the input instance and outputs a value k such that C"o"p"t@?k@?(1+@e)@?C"o"p"t+1, where C"o"p"t is the cost of an optimal solution. It is clear that uniform sampling by itself will not allow a sublinear-time algorithm in this setting; a small number of items might constitute most of the total weight and uniform samples will not hit them. In this work we use weighted samples, where item i is sampled with probability proportional to its weight: that is, with probability w"i @?"iw"i. In the presence of weighted samples, the approximation algorithm runs in O@?(n@?poly(1 @e))+g(1 @e) time, where g(x) is an exponential function of x. When both weighted sampling and uniform sampling are allowed, O@?(n^1^ ^3@?poly(1 @e))+g(1 @e) time suffices. In addition to an approximate value to C"o"p"t, our algorithm can also output a constant-size ''template'' of a packing that can later be used to find a near-optimal packing in linear time. The bin packing problem is to find the minimum number of bins of size one to pack a list of items with sizes a 1 ,…, a n in (0,1]. Using uniform sampling, which selects a random element from the input list each time, we develop a randomized @math time (1+e )-approximation scheme for the bin packing problem. We show that every randomized algorithm with uniform random sampling needs @math time to give an (1+e )-approximation. For each function s (n ): N →N , define ∑(s (n )) to be the set of all bin packing problems with the sum of item sizes equal to s (n ). We show that ∑(n b ) is NP-hard for every b ∈(0,1]. This implies a dense sublinear time hierarchy of approximation schemes for a class of NP-hard problems, which are derived from the bin packing problem. We also show a randomized streaming approximation scheme for the bin packing problem such that it needs only constant updating time and constant space, and outputs an (1+e )-approximation in @math time. Let S (δ )-bin packing be the class of bin packing problems with each input item of size at least δ . This research also gives a natural example of NP-hard problem (S (δ )-bin packing) that has a constant time approximation scheme, and a constant time and space sliding window streaming approximation scheme, where δ is a positive constant.