Karmarkar–Karp bin packing algorithms

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 $\mathrm {OPT} +{\mathcal {O}}(\log ^{2}(OPT))$ 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.

The KK algorithms were considered a breakthrough in the study of bin packing: the previously-known algorithms found multiplicative approximation, where the number of bins was at most $r\cdot \mathrm {OPT} +s$ for some constants Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r>1, s>0} , or at most Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (1+\varepsilon )\mathrm {OPT} +1} . The KK algorithms were the first ones to attain an additive approximation.

Input

The input to a bin-packing problem is a set of items of different sizes, a₁,...a_n. The following notation is used:

• n - the number of items.
• m - the number of different item sizes. For each i in 1,...,m:
  • s_i is the i-th size;
  • n_i is the number of items of size s_i.
• B - the bin size.

Given an instance I, we denote:

• OPT(I) = the optimal solution of instance I.
• FOPT(I) = (a₁+...+a_n)/B = the theoretically-optimal number of bins, when all bins are completely filled with items or item fractions.

Obviously, FOPT(I) ≤ OPT(I).

High-level scheme

The KK algorithms essentially solve the configuration linear program:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{minimize}~~\mathbf{1}\cdot \mathbf{x}~~~\text{s.t.}~~ A \mathbf{x}\geq \mathbf{n}~~~\text{and}~~ \mathbf{x}\geq 0~~~\text{and}~~ \mathbf{x}~\text{is an integer}~} .

Here, A is a matrix with m rows. Each column of A represents a feasible configuration - a multiset of item-sizes, such that the sum of all these sizes is at most B. The set of configurations is C. x is a vector of size C. Each element x_c of x represents the number of times configuration c is used.

• Example: suppose the item sizes are 3,3,3,3,3,4,4,4,4,4, and B=12. Then there are C=10 possible configurations: 3333; 333; 33, 334; 3, 34, 344; 4, 44, 444. The matrix A has two rows: [4,3,2,2,1,1,1,0,0,0] for s=3 and [0,0,0,1,0,1,2,1,2,3] for s=4. The vector n is [5,5] since there are 5 items of each size. A possible optimal solution is x=[1,0,0,0,0,0,1,0,0,1], corresponding to using three bins with configurations 3333, 344, 444.

There are two main difficulties in solving this problem. First, it is an integer linear program, which is computationally hard to solve. Second, the number of variables is C - the number of configurations, which may be enormous. The KK algorithms cope with these difficulties using several techniques, some of which were already introduced by de-la-Vega and Lueker. Here is a high-level description of the algorithm (where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} is the original instance):

• 1-a. Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J} be an instance constructed from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} by removing small items.
  • 2-a. Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} be an instance constructed from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J} by grouping items and rounding the size of items in each group to the highest item in the group.
    • 3-a. Construct the configuration linear program for $K$, without the integrality constraints.
      • 4. Compute a (fractional) solution x for the relaxed linear program.
    • 3-b. Round x to an integral solution for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} .
  • 2-b. "Un-group" the items to get a solution for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J} .
• 1-b. Add the small items to get a solution for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} .

Below, we describe each of these steps in turn.

Step 1. Removing and adding small items

The motivation for removing small items is that, when all items are large, the number of items in each bin must be small, so the number of possible configurations is (relatively) small. We pick some constant Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g\in(0,1)} , and remove from the original instance Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} all items smaller than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g\cdot B} . Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J} be the resulting instance. Note that in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J} , each bin can contain at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/g} items. We pack Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J} and get a packing with some Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_J} bins.

Now, we add the small items into the existing bins in an arbitrary order, as long as there is room. When there is no more room in the existing bins, we open a new bin (as in next-fit bin packing). Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_I} be the number of bins in the final packing. Then:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_I \leq \max(b_J, (1+2 g)\cdot OPT(I) + 1)} .

Proof. If no new bins are opened, then the number of bins remains Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_J} . If a new bin is opened, then all bins except maybe the last one contain a total size of at least Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B - g\cdot B} , so the total instance size is at least Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1-g)\cdot B\cdot (b_I-1)} . Therefore, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle FOPT \geq (1-g)\cdot (b_I-1)} , so the optimal solution needs at least Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1-g)\cdot (b_I-1)} bins. So Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_I \leq OPT/(1-g) + 1 = (1+g+g^2+\ldots) OPT+1 \leq (1+2g) OPT+1} . In particular, by taking g=1/n, we get:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_I \leq \max(b_J, OPT +2 \cdot OPT(I)/n + 1)\leq \max(b_J, OPT +3)} ,

since $OPT(I)\leq n$. Therefore, it is common to assume that all items are larger than 1/n.

Step 2. Grouping and un-grouping items

The motivation for grouping items is to reduce the number of different item sizes, to reduce the number of constraints in the configuration LP. The general grouping process is:

• Order the items by descending size.
• Partition the items into groups.
• For each group, modify the size of all items in the group to the largest size in the group.

There are several different grouping methods.

Linear grouping

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k>1} be an integer parameter. Put the largest Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} items in group 1; the next-largest Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} items in group 2; and so on (the last group might have fewer than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} items). Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J} be the original instance. Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K'} be the first group (the group of the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} largest items), and $K$ the grouped instance without the first group. Then:

• In Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K'} all items have the same size. In Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} the number of different sizes is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m(K) \leq n/k + 1} .
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle OPT(K) \leq OPT(J)} - since group 1 in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J} dominates group 2 in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} (all k items in group 1 are larger than the k items in group 2); similarly, group 2 in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J} dominates group 3 in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} , etc.
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle OPT(K') \leq k} - since it is possible to pack each item in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K'} into a single bin.

Therefore, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle OPT(J) \leq OPT(K\cup K') \leq OPT(K)+OPT(K') \leq OPT(K)+k} . Indeed, given a solution to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_K} bins, we can get a solution to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J} with at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_K+k} bins.

Geometric grouping

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k>1} be an integer parameter. Geometric grouping proceeds in two steps:

• Partition the instance Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J} into several instances Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J_0, J_1, \ldots} such that, in each instance Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J_r} , all sizes are in the interval Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [B/2^{r+1}, B/2^r)} . Note that, if all items in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J} have size at least Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g\cdot B} , then the number of instances is at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \log_2(1/g)} .
• On each instance Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J_r} , perform linear rounding with parameter Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k\cdot 2^r} . Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_r, K'_r} be the resulting instances. Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K := \cup _r K_r} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K' := \cup _r K'_r} .

Then, the number of different sizes is bounded as follows:

• For all r, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m(K'_r) = 1} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m(K_r) \leq n(J_r)/(k\cdot 2^r) + 1} . Since all items in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J_r} are larger than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B/2^{r+1}} , we have Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n(J_r)\leq 2^{r+1} \cdot FOPT(J_r)} , so Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m(K_r) \leq 2 FOPT(J_r)/k + 1} . Summing over all r gives Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m(K) \leq 2 FOPT(J)/k + \log_2(1/g)} .

The number of bins is bounded as follows:

• For all r, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle OPT(K'_r) \leq k} - since Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K'_r} has Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k\cdot 2^r} items, and all of them are smaller than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B/2^r} , so they can be packed into at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} bins.
• Therefore, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle OPT(K') \leq k\cdot \log_2(1/g)} .
• Therefore, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle OPT(J) \leq OPT(K)+OPT(K')\leq OPT(K)+k\cdot \log_2(1/g)} .

Alternative geometric grouping

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k>1} be an integer parameter. Order the items by descending size. Partition them into groups such that the total size in each group is at least Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k\cdot B} . Since the size of each item is less than B, The number of items in each group is at least Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k+1} . The number of items in each group is weakly-increasing. If all items are larger than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g\cdot B} , then the number of items in each group is at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k/g} . In each group, only the larger items are rounded up. This can be done such that:

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m(K) \leq FOPT(J)/k + \ln(1/g)} .
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle OPT(J) \leq OPT(K)+2 k\cdot (2 + \ln(1/g))} .

Step 3. Constructing the LP and rounding the solution

We consider the configuration linear program without the integrality constraints:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{minimize}~~\mathbf{1}\cdot \mathbf{x}~~~\text{s.t.}~~ A \mathbf{x}\geq \mathbf{n}~~~\text{and}~~ \mathbf{x}\geq 0} .

Here, we are allowed to use a fractional number of each configuration.

• Example: suppose there are 31 items of size 3 and 7 items of size 4, and the bin-size is 10. The configurations are: 4, 44, 34, 334, 3, 33, 333. The constraints are [0,0,1,2,1,2,3]*x=31 and [1,2,1,1,0,0,0]*x=7. An optimal solution to the fractional LP is [0,0,0,7,0,0,17/3] That is: there are 7 bins of configuration 334 and 17/3 bins of configuration 333. Note that only two different configurations are needed.

Denote the optimal solution of the linear program by LOPT. The following relations are obvious:

• FOPT(I) ≤ LOPT(I), since FOPT(I) is the (possibly fractional) number of bins when all bins are completely filled with items or fractions of items. Clearly, no solution can be more efficient.
• LOPT(I) ≤ OPT(I), since LOPT(I) is a solution to a minimization problem with fewer constraints.
• OPT(I) < 2*FOPT(I), since in any packing with at least 2*FOPT(I) bins, the sum of the two least-full bins is at most B, so they can be combined into a single bin.

A solution to the fractional LP can be rounded to an integral solution as follows.

Suppose we have a solution x to the fractional LP. We round x into a solution for the integral ILP as follows.

• Let x be an optimal basic feasible solution of the fractional LP. Suppose it as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{c\in C} x_c = b_L} bins (note that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_L} may be a fractional number). Since the fractional LP has m constraints (one for each distinct size), x has at most m nonzero variables, that is, at most m different configurations are used. We construct from x an integral packing consisting of a principal part and a residual part.
• The principal part contains floor(x_c) bins of each configuration c for which x_c > 0.
• For the residual part (denoted by R), we construct two candidate packings:
  • A single bin of each configuration c for which x_c > 0; all in all m bins are needed.
  • A greedy packing, with fewer than 2*FOPT(R) bins (since if there are at least 2*FOPT(R) bins, the two smallest ones can be combined).
• The smallest of these packings requires min(m, 2*FOPT(R)) ≤ average(m, 2*FOPT(R)) = FOPT(R) + m/2.
• Adding to this the rounded-down bins of the principal part yields at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_L+m/2} bins.
• The execution time of this conversion algorithm is O(n log n).

This also implies that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle OPT(I)\leq LOPT(I)+m/2} .

Step 4. Solving the fractional LP

The main challenge in solving the fractional LP is that it may have a huge number of variables - a variable for each possible configuration.

The dual LP

The dual linear program of the fractional LP is:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{maximize}~~\mathbf{n}\cdot \mathbf{y}~~~\text{s.t.}~~ A^T \mathbf{y} \leq \mathbf{1}~~~\text{and}~~ \mathbf{y}\geq 0} .

It has m variables Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_1,\ldots,y_m} , and C constraints - a constraint for each configuration. It has the following economic interpretation. For each size s, we should determine a nonnegative price Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_i} . Our profit is the total price of all items. We want to maximize the profit n y subject to the constraints that the total price of items in each configuration is at most 1. This LP now has only m variables, but a huge number of constraints. Even listing all the constraints is infeasible.

Fortunately, it is possible to solve the problem up to any given precision without listing all the constraints, by using a variant of the ellipsoid method. This variant gets as input, a separation oracle: a function that, given a vector y ≥ 0, returns one of the following two options:

• Assert that y is feasible, that is, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A^T \mathbf{y} \leq \mathbf{1}} ; or -
• Assert that y is infeasible, and return a specific constraint that is violated, that is, a vector a such that $\mathbf {a} \cdot \mathbf {y} >1$.

The ellipsoid method starts with a large ellipsoid, that contains the entire feasible domain Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A^T \mathbf{y} \leq \mathbf{1}} . At each step t, it takes the center Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{y}_t} of the current ellipsoid, and sends it to the separation oracle:

• If the oracle says that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{y}_t} is feasible, then we do an "optimality cut": we cut from the ellipsoid all points y for which Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{n}\cdot \mathbf{y} < \mathbf{n}\cdot \mathbf{y}_t} . These points are definitely not optimal.
• If the oracle says that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{y}_t} is infeasible and violates the constraint a, then we do a "feasibility cut": we cut from the ellipsoid all points y for which Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{a}\cdot \mathbf{y} > 1} . These points are definitely not feasible.

After making a cut, we construct a new, smaller ellipsoid. It can be shown that this process converges to an approximate solution, in time polynomial in the required accuracy.

A separation oracle for the dual LP

We are given some m non-negative numbers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_1,\ldots,y_m} . We have to decide between the following two options:

• For every feasible configuration, the sum of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_i} corresponding to this configuration is at most 1; this means that y is feasible.
• There exists a feasible configuration for which the sum of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_i} is larger than 1; this means that y is infeasible. In this case, we also have to return the configuration.

This problem can be solved by solving a knapsack problem, where the item values are Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_1,\ldots,y_m} , the item weights are Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_1,\ldots,s_m} , and the weight capacity is B (the bin size).

• If the total value of the optimal knapsack solution is at most 1, then we say that y is feasible.
• If the total value of the optimal knapsack solution is larger than 1, then we say that y is infeasible, and the items in the optimal knapsack solution correspond to a configuration that violates a constraint (since Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{a}\cdot \mathbf{y} > 1} for the vector a that corresponds to this configuration).

The knapsack problem can be solved by dynamic programming in pseudo-polynomial time: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(m\cdot V)} , where m is the number of inputs and V is the number of different possible values. To get a polynomial-time algorithm, we can solve the knapsack problem approximately, using input rounding. Suppose we want a solution with tolerance Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta} . We can round each of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_1,\ldots,y_m} down to the nearest multiple of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta} /n. Then, the number of possible values between 0 and 1 is n/Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta} , and the run-time is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(m n /\delta)} . The solution is at least the optimal solution minus Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta} /n.

Ellipsoid method with an approximate separation oracle

The ellipsoid method should be adapted to use an approximate separation oracle. Given the current ellipsoid center Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{y}_t} :

• If the approximate oracle returns a solution with value larger than 1, then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{y}_t} is definitely infeasible, and the solution correspond to a configuration that violates a constraint a. We do a "feasibility cut" in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{y}_t} , cutting the ellipsoid all points y for which Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{a}\cdot \mathbf{y} > 1} .
• If the approximate oracle returns a solution with value at most 1, then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{y}_t} may or may not be feasible, but Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{y}_t} rounded down (denote it by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{z}_t} ) is feasible. By definition of the rounding, we know that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{n}\cdot \mathbf{z}_t \geq \mathbf{n}\cdot \mathbf{y}_t - \mathbf{n}\cdot \mathbf{1}\cdot (\delta/n) = \mathbf{n}\cdot \mathbf{y}_t - \delta} . We still do an "optimality cut" in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{y}_t} : we cut from the ellipsoid all points y for which Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{n}\cdot \mathbf{y} < \mathbf{n}\cdot \mathbf{y}_t} . Note that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{y}_t} might be infeasible, so its value might be larger than OPT. Therefore, we might remove some points whose objective is optimal. However, the removed points satisfy Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{n}\cdot \mathbf{y} < \mathbf{n}\cdot \mathbf{z}_t+\delta \leq \text{OPT}+\delta} ; no point is removed if its value exceeds the value at Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{z}_t} by more than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta} .

Using the approximate separation oracle gives a feasible solution y* to the dual LP, with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{n}\cdot \mathbf{y^*} \geq LOPT-\delta} , after at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q} iterations, where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q = 4m^2 \ln(mn/g\delta)} . The total run-time of the ellipsoid method with the approximate separation oracle is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(Q m n /\delta)} .

Eliminating constraints

During the ellipsoid method, we use at most Q constraints of the form Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{a}\cdot \mathbf{y} \leq 1} . All the other constraints can be eliminated, since they have no effect on the outcome y* of the ellipsoid method. We can eliminate even more constraints. It is known that, in any LP with m variables, there is a set of m constraints that is sufficient for determining the optimal solution (that is, the optimal value is the same even if only these m constraints are used). We can repeatedly run the ellipsoid method as above, each time trying to remove a specific set of constraints. If the resulting error is at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta} , then we remove these constraints permanently. It can be shown that we need at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \approx (Q/m) + m\ln(Q/m)} eliminations, so the accumulating error is at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \approx \delta\cdot [(Q/m) + m\ln(Q/m)]} . If we try sets of constraints deterministically, then in the worst case, one out of m trials succeeds, so we need to run the ellipsoid method at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \approx m\cdot[(Q/m) + m\ln(Q/m)] = Q+m^2\ln(Q/m) } times. If we choose the constraints to remove at random, then the expected number of iterations is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(m)\cdot[1 + \ln(Q/m)]} .

Finally, we have a reduced dual LP, with only m variables and m constraints. The optimal value of the reduced LP is at least Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle LOPT-h} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h \approx \delta\cdot [(Q/m) + m\ln(Q/m)]} .

Solving the primal LP

By the LP duality theorem, the minimum value of the primal LP equals the maximum value of the dual LP, which we denoted by LOPT. Once we have a reduced dual LP, we take its dual, and take a reduced primal LP. This LP has only m variables - corresponding to only m out of C configurations. The maximum value of the reduced dual LP is at least Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle LOPT-h} . It can be shown that the optimal solution of the reduced primal LP is at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle LOPT+h} . The solution gives a near-optimal bin packing, using at most m configurations.

The total run-time of the deterministic algorithm, when all items are larger than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g\cdot B} , is:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O\left(\frac{Q m n}{\delta} \cdot( Q+m^2\ln\frac{Q}{m}) \right) = O \left(\frac{Q^2 m n + Q m^3 n\ln\frac{Q}{m}}{\delta} \right) \approx O\left(m^8 \ln{m} \ln^2(\frac{m n}{g h}) + \frac{m^4 n \ln{m}}{h}\ln(\frac{m n}{g h}) \right)} ,

The expected total run-time of the randomized algorithm is: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O\left(m^7 \log{m} \log^2(\frac{m n}{g h}) + \frac{m^4 n \log{m}}{h}\log(\frac{m n}{g h}) \right)} .

End-to-end algorithms

Karmarkar and Karp presented three algorithms, that use the above techniques with different parameters. The run-time of all these algorithms depends on a function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(\cdot,\cdot)} , which is a polynomial function describing the time it takes to solve the fractional LP with tolerance h=1, which is, for the deterministic version,Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(m,n)\in O(m^8\log{m}\log^2{n} + m^4 n \log{m}\log{n} )} .

Algorithm 1

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon>0} be a constant representing the desired approximation accuracy.

• 1-a. Set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g = \max(1/n, \epsilon/2)} . Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J} be an instance constructed from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} by removing all items smaller than g.
  • 2-a. Set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k = n\cdot \epsilon^2} . Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} be an instance constructed from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J} by linear grouping with parameter k, and let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K'} be the remaining instance (the group of k largest items). Note that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m(K) \leq n/k + 1 \approx 1/\epsilon^2} .
    • 3-a. Construct the configuration linear program for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} , without the integrality constraints.
      • 4. Compute a solution x for $K$, with tolerance h=1. The result is a fractional bin packing with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_L\leq LOPT(K)+1} bins. The run-time is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(m(K),n(K)) \leq T(\epsilon^{-2},n) } .
    • 3-b. Round x to an integral solution for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} . Add at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m(K)/2} bins for the fractional part. The total number of bins is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_K\leq b_L + m(K)/2 \leq LOPT(K)+1 + 1/2\epsilon^2} .
  • 2-b. Pack the items in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K'} using at most k bins; get a packing of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J} . The number of bins is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_J\leq b_K+k \leq LOPT(K)+1 + 1/2\epsilon^2 + n\cdot \epsilon^2} .
• 1-b. Add the items smaller than g to get a solution for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} . The number of bins is: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_I \leq \max(b_J, (1+2 g)\cdot OPT(I) + 1)\leq (1+\epsilon)OPT(I) + 1/2\epsilon^2 + 3} .

All in all, the number of bins is in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1+\epsilon)OPT + O(\epsilon^{-2})} and the run-time is in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n\log n + T(\epsilon^{-2},n))} . By choosing Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon = OPT^{-1/3}} we get Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle OPT + O(OPT^{2/3})} .

Algorithm 2

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g>0} be a real parameter and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k>0} an integer parameter to be determined later.

• 1-a. Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J} be an instance constructed from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} by removing all items smaller than g.
• 2. While Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle FOPT(J) > 1+\frac{k}{k-1}\ln(1/g)} do:
  • 2-a. Do the Alternative Geometric Grouping with parameter k. Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} be the resulting instance, and let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K'} be the remaining instance. We have Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m(K) \leq FOPT(J)/k + \ln(1/g)} .
    • 3-a. Construct the configuration linear program for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} , without the integrality constraints.
      • 4. Compute a solution x for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} , with tolerance h=1. The result is a fractional bin packing with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_L\leq LOPT(K)+1} bins. The run-time is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(m(K),n(K)) \leq T(FOPT(J)/k + \ln(1/g) ,n) } .
    • 3-b. Round x to an integral solution for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} . Do not add bins for the fractional part. Instead, just remove the packed items from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J} .
  • 2-b. Pack the items in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K'} in at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2 k\cdot (2 + \ln(1/g))} bins.
• 2. Once Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle FOPT(J) \leq 1+\frac{k}{k-1}\ln(1/g)} , pack the remaining items greedily into at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2 FOPT(J) \leq 2+\frac{2 k}{k-1}\ln(1/g)} bins.
  • At each iteration of the loop in step 2, the fractional part of x has at most m(K) patterns, so Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle FOPT(J_{t+1}) \leq m(K_{t}) \leq FOPT(J_{t})/k + \ln(1/g)} . The FOPT drops by a factor of k in each iteration, so the number of iterations is at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{\ln FOPT(I)}{\ln k}+1} .
  • Therefore, the total number of bins used for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J} is: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_J \leq OPT(I) + \left[1+\frac{\ln FOPT(I)}{\ln k}\right]\left[1 + 4k + 2k\ln(1/g)\right]+ 2 + \frac{2k}{k-1}\ln(1/g)} .
• 1-b. Add the items smaller than g to get a solution for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} . The number of bins is: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_I \leq \max(b_J, (1+2 g)\cdot OPT(I) + 1)} .

The run-time is in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n\log n + T(FOPT(J)/k + \ln(1/g),n))} .

Now, if we choose k=2 and g=1/FOPT(I), we get:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_J \leq OPT + O(\log^2(FOPT)) } ,

and hence:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_I \leq \max(b_J, OPT+2OPT /FOPT+1) \leq \max(b_J, OPT+5) \in OPT+\log^2(OPT)} ,

so the total number of bins is in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle OPT + O(\log^2(FOPT))} . The run-time is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n\log n) + T(FOPT/2 + \ln(FOPT) ,n)\in O(n\log{n} + T(FOPT, n)) } .

The same algorithm can be used with different parameters to trade-off run-time with accuracy. For some parameter Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha\in(0,1)} , choose Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k=FOPT^{\alpha}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g=1/FOPT^{1-\alpha}} . Then, the packing needs at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{OPT} + \mathcal{O}(OPT^\alpha)} bins, and the run-time is in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n\log{n} + T(FOPT^{(1-\alpha)},n))} .

Algorithm 3

The third algorithm is useful when the number of sizes m is small (see also high-multiplicity bin packing).

• 1-a. Set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g = \frac{\log^2(m)}{FOPT(I)}} . Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} be an instance constructed from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} by removing all items smaller than g.
• If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m(K)\leq FOPT(K)} then:
  • 3-a. Construct the configuration linear program for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} , without the integrality constraints.
    • 4. Compute a solution x for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} , with tolerance h=1. The result is a fractional bin packing with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_L\leq LOPT(K)+1} bins. The run-time is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T(m(K),n(K)) \leq T(\epsilon^{-2},n) } .
  • 3-b. Round x to an integral solution for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} . Do not add bins for the fractional part. Instead, just remove the packed items from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} .
• Run step 2 of Algorithm 2 on the remaining pieces.
• 1-b. Add the items smaller than g to get a solution for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} . The number of bins is: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_I \leq \max(b_J, (1+2 g)\cdot OPT(I) + 1)} .

It uses at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{OPT} + \mathcal{O}(\log^2 m)} bins, and the run-time is in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n\log{n} + T(m,n))} .

Improvements

The KK techniques were improved later, to provide even better approximations.

Rothvoss uses the same scheme as Algorithm 2, but with a different rounding procedure in Step 2. He introduced a "gluing" step, in which small items are glued together to yield a single larger item. This gluing can be used to increase the smallest item size to about Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B/\log^{12}(n)} . When all sizes are at least Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B/\log^{12}(n)} , we can substitute Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g = 1/\log^{12}(n)} in the guarantee of Algorithm 2, and get:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_J \leq OPT(I) + O(\log(FOPT)\log(\log(n)))} ,

which yields a Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{OPT} + O(\log(\mathrm{OPT})\cdot \log\log(\mathrm{OPT}))} bins.

Hoberg and Rothvoss use a similar scheme in which the items are first packed into "containers", and then the containers are packed into bins. Their algorithm needs at most Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_J \leq OPT(I) + O(\log(OPT))} bins.