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.
is an NP-complete problem and indeed it is NP-hard even to decide whether two bins are sufficient or at least three bins are necessary. This follows by a simple reduction from the problem and presents the strongest inapproximability to date. Most work in the offline model focused on providing @math -approximation algorithms, which use at most @math bins. In the following, when we refer to an approximation for we implicitly mean the asymptotic approximation. The first (PTAS), that is, a @math -approximation for any @math , was given by Fernandez de la Vega and Lueker @cite_22 . Karmarkar and Karp @cite_0 provided an algorithm which returns a solution with @math bins. Recently, Hoberg and Rothvo @cite_27 proved it is possible to find a solution with @math bins in polynomial time.
@cite_0 @cite_27 @cite_22
2123068254 2964205596
We present several polynomial-time approximation algorithms for the one-dimensional bin-packing problem. using a subroutine to solve a certain linear programming relaxation of the problem. Our main results are as follows: There is a polynomial-time algorithm A such that A(I) ≤ OPT(I) + O(log2 OPT(I)). There is a polynomial-time algorithm A such that, if m(I) denotes the number of distinct sizes of pieces occurring in instance I, then A(I) ≤ OPT(I) + O(log2 m(I)). There is an approximation scheme which accepts as input an instance I and a positive real number e, and produces as output a packing using as most (1 + e) OPT(I) + O(e-2) bins. Its execution time is O(e-c n log n), where c is a constant. These are the best asymptotic performance bounds that have been achieved to date for polynomial-time bin-packing. Each of our algorithms makes at most O(log n) calls on the LP relaxation subroutine and takes at most O(n log n) time for other operations. The LP relaxation of bin packing was solved efficiently in practice by Gilmore and Gomory. We prove its membership in P, despite the fact that it has an astronomically large number of variables. For bin packing, the input consists of n items with sizes s1,...,sn ∈ [0,1] which have to be assigned to a minimum number of bins of size 1. Recently, the second author gave an LP-based polynomial time algorithm that employed techniques from discrepancy theory to find a solution using at most OPT + O(logOPT·loglogOPT) bins. In this paper, we build on the techniques of Rothvoss to present an approximation algorithm that has an additive gap of only O(logOPT) bins. This gap matches certain combinatorial lower bounds, and any further improvement would have to use more algebraic structure.