Karmarkar and Karp devised an algorithm that runs in polynomial time and finds a solution with at most
They also devised several other algorithms with slightly different approximation guarantees and run-time bounds.
The input to a bin-packing problem is a set of items of different sizes, a1,...an.
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:
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.
First, it is an integer linear program, which is computationally hard to solve.
The KK algorithms cope with these difficulties using several techniques, some of which were already introduced by de-la-Vega and Lueker.
Now, we add the small items into the existing bins in an arbitrary order, as long as there is room.
Denote the optimal solution of the linear program by LOPT.
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.
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: The ellipsoid method starts with a large ellipsoid, that contains the entire feasible domain
It can be shown that this process converges to an approximate solution, in time polynomial in the required accuracy.
The knapsack problem can be solved by dynamic programming in pseudo-polynomial time:
To get a polynomial-time algorithm, we can solve the knapsack problem approximately, using input rounding.
The ellipsoid method should be adapted to use an approximate separation oracle.
: Using the approximate separation oracle gives a feasible solution y* to the dual LP, with
The total run-time of the ellipsoid method with the approximate separation oracle is
All the other constraints can be eliminated, since they have no effect on the outcome y* of the ellipsoid method.
We can repeatedly run the ellipsoid method as above, each time trying to remove a specific set of constraints.
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
If we choose the constraints to remove at random, then the expected number of iterations is
Finally, we have a reduced dual LP, with only m variables and m constraints.
It can be shown[clarification needed] that the optimal solution of the reduced primal LP is at most
The total run-time of the deterministic algorithm, when all items are larger than
Karmarkar and Karp presented three algorithms, that use the above techniques with different parameters.
, 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,
The third algorithm is useful when the number of sizes m is small (see also high-multiplicity bin packing).
Rothvoss[4] uses the same scheme as Algorithm 2, but with a different rounding procedure in Step 2.