Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 09:59, 13 January 2022

Revision as of 10:58, 13 January 2022

Line 96:

** 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 LOPT(I)at +most ''<math>b_L+m''/2</math> bins.{{Clarify|date=January 2022}}

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

Therefore,This also implies that <math>OPT(I) ≤\leq LOPT(I) + ''m''/2:</math>.

== Step 4. Solving the fractional LP ==