Karmarkar–Karp bin packing algorithms

Let ${\displaystyle k>1}$ be an integer parameter. Put the largest ${\displaystyle k}$ items in group 1; the next-largest ${\displaystyle k}$ items in group 2; and so on (the last group might have fewer than ${\displaystyle k}$ items). Let ${\displaystyle J}$ be the original instance. Let ${\displaystyle K'}$ be the first group (the group of the ${\displaystyle k}$ largest items), and ${\displaystyle K}$ the grouped instance without the first group. Then:

• In ${\displaystyle K'}$ all items have the same size. In ${\displaystyle K}$ the number of different sizes is ${\displaystyle m(K)\leq n/k+1}$.
• ${\displaystyle OPT(K)\leq OPT(J)}$ - since group 1 in ${\displaystyle J}$ dominates group 2 in ${\displaystyle K}$ (all k items in group 1 are larger than the k items in group 2); similarly, group 2 in ${\displaystyle J}$ dominates group 3 in ${\displaystyle K}$, etc.
• ${\displaystyle OPT(K')\leq k}$ - since it is possible to pack each item in ${\displaystyle K'}$ into a single bin.

Therefore, ${\displaystyle OPT(J)\leq OPT(K\cup K')\leq OPT(K)+OPT(K')\leq OPT(K)+k}$. Indeed, given a solution to ${\displaystyle K}$ with ${\displaystyle b_{K}}$ bins, we can get a solution to ${\displaystyle J}$ with at most ${\displaystyle b_{K}+k}$ bins.

Let ${\displaystyle k>1}$ be an integer parameter. Geometric grouping proceeds in two steps:

• Partition the instance ${\displaystyle J}$ into several instances ${\displaystyle J_{0},J_{1},\ldots }$ such that, in each instance ${\displaystyle J_{r}}$, all sizes are in the interval ${\displaystyle [B/2^{r+1},B/2^{r})}$. Note that, if all items in ${\displaystyle J}$ have size at least ${\displaystyle g\cdot B}$, then the number of instances is at most ${\displaystyle \log _{2}(1/g)}$.
• On each instance ${\displaystyle J_{r}}$, perform linear rounding with parameter ${\displaystyle k\cdot 2^{r}}$. Let ${\displaystyle K_{r},K'_{r}}$ be the resulting instances. Let ${\displaystyle K:=\cup _{r}K_{r}}$ and ${\displaystyle K':=\cup _{r}K'_{r}}$.

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

• For all r, ${\displaystyle m(K'_{r})=1}$ and ${\displaystyle m(K_{r})\leq n(J_{r})/(k\cdot 2^{r})+1}$. Since all items in ${\displaystyle J_{r}}$ are larger than ${\displaystyle B/2^{r+1}}$, we have ${\displaystyle n(J_{r})\leq 2^{r+1}\cdot FOPT(J_{r})}$, so ${\displaystyle m(K_{r})\leq 2FOPT(J_{r})/k+1}$. Summing over all r gives ${\displaystyle m(K)\leq 2FOPT(J)/k+\log _{2}(1/g)}$.

The number of bins is bounded as follows:

• For all r, ${\displaystyle OPT(K'_{r})\leq k}$ - since ${\displaystyle K'_{r}}$ has ${\displaystyle k\cdot 2^{r}}$ items, and all of them are smaller than ${\displaystyle B/2^{r}}$, so they can be packed into at most ${\displaystyle k}$ bins.
• Therefore, ${\displaystyle OPT(K')\leq k\cdot \log _{2}(1/g)}$.
• Therefore, ${\displaystyle OPT(J)\leq OPT(K)+OPT(K')\leq OPT(K)+k\cdot \log _{2}(1/g)}$.

Let ${\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 ${\displaystyle k\cdot B}$. Since the size of each item is less than B, The number of items in each group is at least ${\displaystyle k+1}$. The number of items in each group is weakly-increasing. If all items are larger than ${\displaystyle g\cdot B}$, then the number of items in each group is at most ${\displaystyle k/g}$. In each group, only the larger items are rounded up. This can be done such that:

• ${\displaystyle m(K)\leq FOPT(J)/k+\ln(1/g)}$.
• ${\displaystyle OPT(J)\leq OPT(K)+2k\cdot (2+\ln(1/g))}$.

The dual linear program of the fractional LP is:

${\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 ${\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 ${\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, ${\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 ${\displaystyle \mathbf {a} \cdot \mathbf {y} >1}$.

The ellipsoid method starts with a large ellipsoid, that contains the entire feasible domain ${\displaystyle A^{T}\mathbf {y} \leq \mathbf {1} }$. At each step t, it takes the center ${\displaystyle \mathbf {y} _{t}}$ of the current ellipsoid, and sends it to the separation oracle:

• If the oracle says that ${\displaystyle \mathbf {y} _{t}}$ is feasible, then we do an "optimality cut": we cut from the ellipsoid all points y for which ${\displaystyle \mathbf {n} \cdot \mathbf {y} <\mathbf {n} \cdot \mathbf {y} _{t}}$. These points are definitely not optimal.
• If the oracle says that ${\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 ${\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.

We are given some m non-negative numbers ${\displaystyle y_{1},\ldots ,y_{m}}$. We have to decide between the following two options:

• For every feasible configuration, the sum of ${\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 ${\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 ${\displaystyle y_{1},\ldots ,y_{m}}$, the item weights are ${\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 ${\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: ${\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 ${\displaystyle \delta }$. We can round each of ${\displaystyle y_{1},\ldots ,y_{m}}$ down to the nearest multiple of ${\displaystyle \delta }$/n. Then, the number of possible values between 0 and 1 is n/${\displaystyle \delta }$, and the run-time is ${\displaystyle O(mn/\delta )}$. The solution is at least the optimal solution minus ${\displaystyle \delta }$/n.

The ellipsoid method should be adapted to use an approximate separation oracle. Given the current ellipsoid center ${\displaystyle \mathbf {y} _{t}}$:

• If the approximate oracle returns a solution with value larger than 1, then ${\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 ${\displaystyle \mathbf {y} _{t}}$, cutting the ellipsoid all points y for which ${\displaystyle \mathbf {a} \cdot \mathbf {y} >1}$.
• If the approximate oracle returns a solution with value at most 1, then ${\displaystyle \mathbf {y} _{t}}$ may or may not be feasible, but ${\displaystyle \mathbf {y} _{t}}$ rounded down (denote it by ${\displaystyle \mathbf {z} _{t}}$) is feasible. By definition of the rounding, we know that ${\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 ${\displaystyle \mathbf {y} _{t}}$: we cut from the ellipsoid all points y for which ${\displaystyle \mathbf {n} \cdot \mathbf {y} <\mathbf {n} \cdot \mathbf {y} _{t}}$. Note that ${\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 ${\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 ${\displaystyle \mathbf {z} _{t}}$by more than ${\displaystyle \delta }$.

Using the approximate separation oracle gives a feasible solution y* to the dual LP, with ${\displaystyle \mathbf {n} \cdot \mathbf {y^{*}} \geq LOPT-\delta }$, after at most ${\displaystyle Q}$ iterations, where ${\displaystyle Q=4m^{2}\ln(mn/g\delta )}$. The total run-time of the ellipsoid method with the approximate separation oracle is ${\displaystyle O(Qmn/\delta )}$.

During the ellipsoid method, we use at most Q constraints of the form ${\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 ${\displaystyle \delta }$, then we remove these constraints permanently. It can be shown that we need at most ${\displaystyle \approx (Q/m)+m\ln(Q/m)}$ eliminations, so the accumulating error is at most ${\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 ${\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 ${\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 ${\displaystyle LOPT-h}$, where ${\displaystyle h\approx \delta \cdot [(Q/m)+m\ln(Q/m)]}$.

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 ${\displaystyle LOPT-h}$. It can be shown that the optimal solution of the reduced primal LP is at most ${\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 ${\displaystyle g\cdot B}$, is:

${\displaystyle O\left({\frac {Qmn}{\delta }}\cdot (Q+m^{2}\ln {\frac {Q}{m}})\right)=O\left({\frac {Q^{2}mn+Qm^{3}n\ln {\frac {Q}{m}}}{\delta }}\right)\approx O\left(m^{8}\ln {m}\ln ^{2}({\frac {mn}{gh}})+{\frac {m^{4}n\ln {m}}{h}}\ln({\frac {mn}{gh}})\right)}$,

The expected total run-time of the randomized algorithm is: ${\displaystyle O\left(m^{7}\log {m}\log ^{2}({\frac {mn}{gh}})+{\frac {m^{4}n\log {m}}{h}}\log({\frac {mn}{gh}})\right)}$.

Let ${\displaystyle \epsilon >0}$ be a constant representing the desired approximation accuracy.

• 1-a. Set ${\displaystyle g=\max(1/n,\epsilon /2)}$. Let ${\displaystyle J}$ be an instance constructed from ${\displaystyle I}$ by removing all items smaller than g.
  • 2-a. Set ${\displaystyle k=n\cdot \epsilon ^{2}}$. Let ${\displaystyle K}$ be an instance constructed from ${\displaystyle J}$ by linear grouping with parameter k, and let ${\displaystyle K'}$ be the remaining instance (the group of k largest items). Note that ${\displaystyle m(K)\leq n/k+1\approx 1/\epsilon ^{2}}$.
    • 3-a. Construct the configuration linear program for ${\displaystyle K}$, without the integrality constraints.
      • 4. Compute a solution x for ${\displaystyle K}$, with tolerance h=1. The result is a fractional bin packing with ${\displaystyle b_{L}\leq LOPT(K)+1}$ bins. The run-time is ${\displaystyle T(m(K),n(K))\leq T(\epsilon ^{-2},n)}$.
    • 3-b. Round x to an integral solution for ${\displaystyle K}$. Add at most ${\displaystyle m(K)/2}$ bins for the fractional part. The total number of bins is ${\displaystyle b_{K}\leq b_{L}+m(K)/2\leq LOPT(K)+1+1/2\epsilon ^{2}}$.
  • 2-b. Pack the items in ${\displaystyle K'}$ using at most k bins; get a packing of ${\displaystyle J}$. The number of bins is ${\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 ${\displaystyle I}$. The number of bins is: ${\displaystyle b_{I}\leq \max(b_{J},(1+2g)\cdot OPT(I)+1)\leq (1+\epsilon )OPT(I)+1/2\epsilon ^{2}+3}$.

All in all, the number of bins is in ${\displaystyle (1+\epsilon )OPT+O(\epsilon ^{-2})}$ and the run-time is in ${\displaystyle O(n\log n+T(\epsilon ^{-2},n))}$. By choosing ${\displaystyle \epsilon =OPT^{-1/3}}$ we get ${\displaystyle OPT+O(OPT^{2/3})}$.

Let ${\displaystyle g>0}$ be a real parameter and ${\displaystyle k>0}$ an integer parameter to be determined later.

• 1-a. Let ${\displaystyle J}$ be an instance constructed from ${\displaystyle I}$ by removing all items smaller than g.
• 2. While ${\displaystyle FOPT(J)>1+{\frac {k}{k-1}}\ln(1/g)}$ do:
  • 2-a. Do the Alternative Geometric Grouping with parameter k. Let ${\displaystyle K}$ be the resulting instance, and let ${\displaystyle K'}$ be the remaining instance. We have ${\displaystyle m(K)\leq FOPT(J)/k+\ln(1/g)}$.
    • 3-a. Construct the configuration linear program for ${\displaystyle K}$, without the integrality constraints.
      • 4. Compute a solution x for ${\displaystyle K}$, with tolerance h=1. The result is a fractional bin packing with ${\displaystyle b_{L}\leq LOPT(K)+1}$ bins. The run-time is ${\displaystyle T(m(K),n(K))\leq T(FOPT(J)/k+\ln(1/g),n)}$.
    • 3-b. Round x to an integral solution for ${\displaystyle K}$. Do not add bins for the fractional part. Instead, just remove the packed items from ${\displaystyle J}$.
  • 2-b. Pack the items in ${\displaystyle K'}$ in at most ${\displaystyle 2k\cdot (2+\ln(1/g))}$ bins.
• 2. Once ${\displaystyle FOPT(J)\leq 1+{\frac {k}{k-1}}\ln(1/g)}$, pack the remaining items greedily into at most ${\displaystyle 2FOPT(J)\leq 2+{\frac {2k}{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 ${\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 ${\displaystyle {\frac {\ln FOPT(I)}{\ln k}}+1}$.
  • Therefore, the total number of bins used for ${\displaystyle J}$ is: ${\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 ${\displaystyle I}$. The number of bins is: ${\displaystyle b_{I}\leq \max(b_{J},(1+2g)\cdot OPT(I)+1)}$.

The run-time is in ${\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:

${\displaystyle b_{J}\leq OPT+O(\log ^{2}(FOPT))}$,

and hence:

${\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 ${\displaystyle OPT+O(\log ^{2}(FOPT))}$. The run-time is ${\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 ${\displaystyle \alpha \in (0,1)}$, choose ${\displaystyle k=FOPT^{\alpha }}$ and ${\displaystyle g=1/FOPT^{1-\alpha }}$. Then, the packing needs at most ${\displaystyle \mathrm {OPT} +{\mathcal {O}}(OPT^{\alpha })}$ bins, and the run-time is in ${\displaystyle O(n\log {n}+T(FOPT^{(1-\alpha )},n))}$.

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

• 1-a. Set ${\displaystyle g={\frac {\log ^{2}(m)}{FOPT(I)}}}$. Let ${\displaystyle K}$ be an instance constructed from ${\displaystyle I}$ by removing all items smaller than g.
• If ${\displaystyle m(K)\leq FOPT(K)}$ then:
  • 3-a. Construct the configuration linear program for ${\displaystyle K}$, without the integrality constraints.
    • 4. Compute a solution x for ${\displaystyle K}$, with tolerance h=1. The result is a fractional bin packing with ${\displaystyle b_{L}\leq LOPT(K)+1}$ bins. The run-time is ${\displaystyle T(m(K),n(K))\leq T(\epsilon ^{-2},n)}$.
  • 3-b. Round x to an integral solution for ${\displaystyle K}$. Do not add bins for the fractional part. Instead, just remove the packed items from ${\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 ${\displaystyle I}$. The number of bins is: ${\displaystyle b_{I}\leq \max(b_{J},(1+2g)\cdot OPT(I)+1)}$.

It uses at most ${\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log ^{2}m)}$ bins, and the run-time is in ${\displaystyle O(n\log {n}+T(m,n))}$.