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.
We consider the vector scheduling problem, a natural generalization of the classical makespan minimization problem to multiple resources. Here, we are given n jobs represented as d-dimensional vectors in [0,1] d and m identical machines, and the goal is to assign the jobs to machines such that the maximum load of each machine over all the coordinates is at most 1. We study the approximability of multidimensional generalizations of three classical packing problems: multiprocessor scheduling, bin packing, and the knapsack problem. Specifically, we study the vector scheduling problem, its dual problem, namely, the vector bin packing problem, and a class of packing integer programs. The vector scheduling problem is to schedule n d-dimensional tasks on m machines such that the maximum load over all dimensions and all machines is minimized. The vector bin packing problem, on the other hand, seeks to minimize the number of bins needed to schedule all n tasks such that the maximum load on any dimension across all bins is bounded by a fixed quantity, say, 1. Such problems naturally arise when scheduling tasks that have multiple resource requirements. Finally, packing integer programs capture a core problem that directly relates to both vector scheduling and vector bin packing, namely, the problem of packing a maximum number of vectors in a single bin of unit height. We obtain a variety of new algorithmic as well as inapproximability results for these three problems. The resampling algorithm of Moser & Tardos is a powerful approach to develop constructive versions of the Lovasz Local Lemma (LLL). We generalize this to partial resampling: when a bad event holds, we resample an appropriately-random subset of the variables that define this event, rather than the entire set as in Moser & Tardos. This is particularly useful when the bad events are determined by sums of random variables. This leads to several improved algorithmic applications in scheduling, graph transversals, packet routing etc. For instance, we improve the approximation ratio of a generalized @math -dimensional scheduling problem studied by Azar & Epstein from @math to @math , and settle a conjecture of Szabo & Tardos on graph transversals asymptotically. As a point of comparison with the MT algorithm, we show a family of constraint satisfaction problems that does not have "locality" (every constraint is affected by every variable), and so the LLL and the Moser-Tardos algorithm do not give any useful results; however, our method gives strong scale-free approximation ratios and terminates in expected polynomial time for this family. Modern data centers face a key challenge of effectively serving user requests that arrive online. Such requests are inherently multidimensional and characterized by demand vectors over multiple res...