Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 09:50, 13 January 2022

Revision as of 09:59, 13 January 2022

Line 76:

* <math>OPT(J) \leq OPT(K)+2 k\cdot (2 + \ln(1/g))</math>.

== Step 3. Constructing the LP and rounding the LPsolution ==

We consider the [[configuration linear program]] without the integrality constraints:<blockquote><math>\text{minimize}~~\mathbf{1}\cdot \mathbf{x}~~~\text{s.t.}~~ A \mathbf{x}\geq \mathbf{n}~~~\text{and}~~ \mathbf{x}\geq 0</math>.</blockquote>Here, we are allowed to use a fractional number of each configuration.

Line 86:

* 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.

GivenSuppose anwe optimalhave a solution '''x''' to the fractional LP,. itWe canround be rounded'''x''' into a solution for the integral ILP, provingas that OPT(I) ≤ LOPT(I) + ''m''/2:follows.

=== Rounding the fractional LP ===

Given an optimal solution to the fractional LP, it can be rounded into a solution for the integral ILP, proving that OPT(I) ≤ LOPT(I) + ''m''/2:

* Let '''x''' be an optimal [[basic feasible solution]] of the fractional LP. By definition,Suppose theit valueas of<math>\sum_{c\in '''x'''C} isx_c = b_L</math> bins LOPT(Inote that <math>b_L</math> may be a fractional number). Since the fractional LP has ''Sm'' constraints (one for each distinct size), '''x''' has at most ''Sm'' nonzero variables, that is, at most ''Sm'' 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 ''Sm'' 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(S''m'', 2*FOPT(''R'')) ≤ average(S''m'', 2*FOPT(''R'')) = FOPT(R) + S''m''/2.

* Adding to this the rounded-down bins of the principal part yields LOPT(I) + S''m''/2.

* The execution time of this conversion algorithm is O(''n'' log ''n'').

Therefore, OPT(I) ≤ LOPT(I) + ''m''/2:

---

''e'' - a fraction in (0,1), such that ''eB'' is the smallest size of an item.

== Step 4. Solving the fractional LP ==