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 ${\displaystyle \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 ${\displaystyle r\cdot \mathrm {OPT} +s}$ for some constants ${\displaystyle r>1,s>0}$, or at most ${\displaystyle (1+\varepsilon )\mathrm {OPT} +1}$. The KK algorithms were the first ones to attain an additive approximation.

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

Given an instance I, we denote:

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

The KK algorithms essentially solve the configuration linear program:

${\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.