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.
proves to be substantially harder to approximate, even in a constant dimension. For fixed @math , Bansal, Eli ' a s , and Khan @cite_35 showed an approximation factor of @math . For general @math , a relatively simple algorithm based on an LP relaxation, due to Chekuri and Khanna @cite_9 , remains the best known, with an approximation guarantee of @math . The problem is APX-hard even for @math @cite_6 , and cannot be approximated within a factor better than @math for any fixed @math @cite_8 if @math is arbitrarily large. Hence, our streaming @math -approximation for asymptotically achieves the offline lower bound.
@cite_35 @cite_9 @cite_6 @cite_8
2293524428 2042276676 2117812463 2577702044
We study the d-dimensional vector bin packing problem, a well-studied generalization of bin packing arising in resource allocation and scheduling problems. Here we are given a set of d-dimensional vectors v1,..., vn in [0,1]d, and the goal is to pack them into the least number of bins so that for each bin B, the sum of the vectors in it is at most 1 in every dimension, i.e., ||ΣvieB vi||∞ ≤ 1. For the 2-dimensional case we give an asymptotic approximation guarantee of 1 + ln(1.5) + e a (1.405 + e), improving upon the previous bound of 1 + ln 2 + e a (1.693 + e). We also give an almost tight (1.5 + e) absolute approximation guarantee, improving upon the previous bound of 2 [23]. For the d-dimensional case, we get a 1.5 + ln([EQUATION]) + e a 0.807 + ln(d + 1) + e guarantee, improving upon the previous (1+ln d+e) guarantee [2]. Here (1 + ln d) was a natural barrier as rounding-based algorithms can not achieve better than d approximation. We get around this by exploiting various structural properties of (near)-optimal packings, and using multi-objective multi-budget matching based techniques and expanding the Round & Approx framework to go beyond rounding-based algorithms. Along the way we also prove several results that could be of independent interest. 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 d-dimensional vector packing problem is a well-known generalization of the classical bin packing problem: For a given list of vectors in [0, 1]d, the goal is to partition the list into the minimum number of subsets, such that in every subset the sum of all vectors is at most one in every coordinate. For the case d = 1, Fernandez de la Vega and Lueker (1981) designed an asymptotic polynomial time approximation scheme. In this note we prove that already for the case d = 2, the existence of an asymptotic polynomial time approximation scheme would imply P = NP. The proof is very simple and uses no new ideas. Abstract The bin packing problem is a well-studied problem in combinatorial optimization. In the classical bin packing problem, we are given a list of real numbers in ( 0 , 1 ] and the goal is to place them in a minimum number of bins so that no bin holds numbers summing to more than 1. The problem is extremely important in practice and finds numerous applications in scheduling, routing and resource allocation problems. Theoretically the problem has rich connections with discrepancy theory, iterative methods, entropy rounding and has led to the development of several algorithmic techniques. In this survey we consider approximation and online algorithms for several classical generalizations of bin packing problem such as geometric bin packing, vector bin packing and various other related problems. There is also a vast literature on mathematical models and exact algorithms for bin packing. However, this survey does not address such exact algorithms. In two-dimensional geometric bin packing , we are given a collection of rectangular items to be packed into a minimum number of unit size square bins. This variant has a lot of applications in cutting stock, vehicle loading, pallet packing, memory allocation and several other logistics and robotics related problems. In d -dimensional vector bin packing , each item is a d -dimensional vector that needs to be packed into unit vector bins. This problem is of great significance in resource constrained scheduling and in recent virtual machine placement in cloud computing. We also consider several other generalizations of bin packing such as geometric knapsack, strip packing and other related problems such as vector scheduling, vector covering etc. We survey algorithms for these problems in offline and online setting, and also mention results for several important special cases. We briefly mention related techniques used in the design and analysis of these algorithms. In the end we conclude with a list of open problems.