 | This article needs additional citations for verification .(February 2022) |
High-multiplicity bin packing is a special case of the bin packing problem, in which the number of different item-sizes is small, while the number of items with each size is large. While the general bin-packing problem is NP-hard, the high-multiplicity setting can be solved in polynomial time, assuming that the number of different sizes is a fixed constant.
The inputs to the problem are positive integers:
The output is a packing - an assignment of the items to bins, such that the total size of items in each bin is at most B, and subject to this, the number of bins is as small as possible.
Example: suppose d=2, s1=30, s2=40, n1=n2=5, B=120. So there are n=10 items with sizes: 30,30,30,30,30,40,40,40,40,40. Then, a possible packing is: {30,30,30,30}, {40,40,40}, {30,40,40}, which uses 3 bins.
A configuration is a set of items that can fit into a single bin. It can be represented by a vector of d integers, denoting the multiplicities of the different sizes in the configuration. Formally, for each configuration c we define an integer vector ac=ac,1, ..., ac,d such that ac ≤ n and ac·s ≤ B.
In the above example, one of the configurations is c={30,40,40}, since 1*30+2*40 ≤ 120. Its corresponding vector is ac=(1,2). Other configuration vectors are (4,0), (3,0), (2,0), (2,1), (1,0), (1,1), (1,2), (0,1), (0,2), (0,3). If we had only three items of size 3, then we could not use the (4,0) configuration.
It is possible to present the problem using the configuration linear program : for each configuration c, there is a variable xc, denoting the number of bins in which c is used. The total number of bins used is simply the sum of xc over all configurations, denoted by 1·x. The total number of items used from each size is the sum of the vectors ac · xc over all configurations c. Then, the problem is to minimize 1·x such that the sum of ac · xc, over all configurations c, is at least n, so that all items are packed.
Suppose first that all items are large, that is, every si is at least e·B for some fraction e>0. Then, the total number of items in each bin is at most 1/e, so the total number of configuration is at most d1/e. Each configuration appears at most n times. Therefore, there are at most combinations to check. For each combination, we have to check d constraints (one for each size), so the run-time is , which is polynomial in n when d, e are constant. [1]
The main problem with this algorithm (besides the fact that it works only when the items are large) is that its runtime is polynomial in n, but the length of the input (in binary representation) is linear in log(V), which is of the order of magnitude of log(n).
Filippi and Agnetis [2] presented an algorithm that finds a solution with at most OPT+d-2 bins in time O(poly(log V)). In particular, for d=2 different sizes, their algorithm finds an optimal solution in time O(log V).
Goemans and Rothvoss [3] [4] presented an algorithm for any fixed d, that finds the optimal solution when all numbers are given in binary encoding. Their algorithm solves the following problem: given two d-dimensional polytopes P and Q, find the minimum number of integer points in P whose sum lies in Q. Their algorithm runs in time . Their algorithm can be adapted to other problems, such as Identical-machines scheduling and unrelated-machines scheduling with various constraints.
Several approximation algorithms for the general bin-packing problem use the following scheme:
The algorithms differ in how they round the instance.
Lueker and de-la-Vega and [5] invented the idea of adaptive input rounding. Order the items by their size, and group them into 1/e2 groups of cardinality ne2. In each group, round the sizes upwards to the maximum size in the group. Now, there are only d=1/e2 different sizes. The solution of the rounded instance is feasible for the original instance too, but the number of bins may be larger than necessary. To quantify the loss, consider the instance rounded down to the maximum size in the previous group (the first group is rounded down to 0). The rounded-down instance D is almost equal to the rounded-up instance U, except that in D there are some ne2 zeros while in U there are some ne2 large items instead; but their size is at most B. Therefore, U requires at most ne2 more bins than D. Since D requires fewer bins than the optimum, we get that Bins(U) ≤ OPT + ne2, that is, we have an additive error that can be made as small as we like by choosing e.
If all items are large (of size at least eB), then each bin in OPT contains at most 1/e items (of size at least eB), so OPT must be at least en. Therefore, Bins(U) ≤ (1+e)OPT. After handling the small items, we get at most .
Karmarkar and Karp [6] present a more efficient rounding method which they call geometric rounding (in contrast to the linear rounding of de-la-Vega and Lueker). Based on these innovations, they present an algorithm with run-time polynomial in and . Their algorithm finds a solution with size at most .
This technique was later improved by several authors:
The knapsack problem is the following problem in combinatorial optimization:
The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in media, and technology mapping in FPGA semiconductor chip design.
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints are linear.
A fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximate solutions to function problems, especially optimization problems. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It returns as output a value is at least times the correct value, and at most times the correct value.
In cryptography, learning with errors (LWE) is a mathematical problem that is widely used to create secure encryption algorithms. It is based on the idea of representing secret information as a set of equations with errors. In other words, LWE is a way to hide the value of a secret by introducing noise to it. In more technical terms, it refers to the computational problem of inferring a linear -ary function over a finite ring from given samples some of which may be erroneous. The LWE problem is conjectured to be hard to solve, and thus to be useful in cryptography.
In computational geometry, a maximum disjoint set (MDS) is a largest set of non-overlapping geometric shapes selected from a given set of candidate shapes.
The geometric set cover problem is the special case of the set cover problem in geometric settings. The input is a range space where is a universe of points in and is a family of subsets of called ranges, defined by the intersection of and geometric shapes such as disks and axis-parallel rectangles. The goal is to select a minimum-size subset of ranges such that every point in the universe is covered by some range in .
The strip packing problem is a 2-dimensional geometric minimization problem. Given a set of axis-aligned rectangles and a strip of bounded width and infinite height, determine an overlapping-free packing of the rectangles into the strip minimizing its height. This problem is a cutting and packing problem and is classified as an Open Dimension Problem according to Wäscher et al.
In computer science, multiway number partitioning is the problem of partitioning a multiset of numbers into a fixed number of subsets, such that the sums of the subsets are as similar as possible. It was first presented by Ronald Graham in 1969 in the context of the identical-machines scheduling problem. The problem is parametrized by a positive integer k, and called k-way number partitioning. The input to the problem is a multiset S of numbers, whose sum is k*T.
In the bin covering problem, items of different sizes must be packed into a finite number of bins or containers, each of which must contain at least a certain given total size, in a way that maximizes the number of bins used.
The multifit algorithm is an algorithm for multiway number partitioning, originally developed for the problem of identical-machines scheduling. It was developed by Coffman, Garey and Johnson. Its novelty comes from the fact that it uses an algorithm for another famous problem - the bin packing problem - as a subroutine.
Identical-machines scheduling is an optimization problem in computer science and operations research. We are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m identical machines, such that a certain objective function is optimized, for example, the makespan is minimized.
Next-fit is an online algorithm for bin packing. Its input is a list of items of different sizes. Its output is a packing - a partition of the items into bins of fixed capacity, such that the sum of sizes of items in each bin is at most the capacity. Ideally, we would like to use as few bins as possible, but minimizing the number of bins is an NP-hard problem. The next-fit algorithm uses the following heuristic:
Best-fit is an online algorithm for bin packing. Its input is a list of items of different sizes. Its output is a packing - a partition of the items into bins of fixed capacity, such that the sum of sizes of items in each bin is at most the capacity. Ideally, we would like to use as few bins as possible, but minimizing the number of bins is an NP-hard problem. The best-fit algorithm uses the following heuristic:
First-fit (FF) is an online algorithm for bin packing. Its input is a list of items of different sizes. Its output is a packing - a partition of the items into bins of fixed capacity, such that the sum of sizes of items in each bin is at most the capacity. Ideally, we would like to use as few bins as possible, but minimizing the number of bins is an NP-hard problem. The first-fit algorithm uses the following heuristic:
First-fit-decreasing (FFD) is an algorithm for bin packing. Its input is a list of items of different sizes. Its output is a packing - a partition of the items into bins of fixed capacity, such that the sum of sizes of items in each bin is at most the capacity. Ideally, we would like to use as few bins as possible, but minimizing the number of bins is an NP-hard problem, so we use an approximately-optimal heuristic.
The configuration linear program (configuration-LP) is a linear programming technique used for solving combinatorial optimization problems. It was introduced in the context of the cutting stock problem. Later, it has been applied to the bin packing and job scheduling problems. In the configuration-LP, there is a variable for each possible configuration - each possible multiset of items that can fit in a single bin. Usually, the number of configurations is exponential in the problem size, but in some cases it is possible to attain approximate solutions using only a polynomial number of configurations.
The Karmarkar–Karp (KK) bin packing algorithms are several related approximation algorithm for the bin packing problem. The bin packing problem is a problem of packing items of different sizes into bins of identical capacity, such that the total number of bins is as small as possible. Finding the optimal solution is computationally hard. Karmarkar and Karp devised an algorithm that runs in polynomial time and finds a solution with at most bins, where OPT is the number of bins in the optimal solution. They also devised several other algorithms with slightly different approximation guarantees and run-time bounds.
