Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 11:28, 14 January 2022

Revision as of 11:31, 14 January 2022

Line 193:

<math>b_J \leq OPT + O(\log^2(FOPT)) </math>, and similarly <math>b_I \leq \max(b_J, OPT+2OPT /FOPT+1) \in OPT+\log^2(OPT) \leq \max(b_J, OPT+5)</math>, so the total number of bins is in <math>OPT + O(\log^2(FOPT))</math>. The run-time is <math>T(FOPT/2 + \ln(FOPT) ,n)\in O(T(FOPT, n)) </math>.

*

*The Atsame algorithm can be used with different parameters to trade-off run-time with accuracy. For some parameter <math>\alpha\in(0,1)</math>, choose <math>k=FOPT^{\alpha}</math> and <math>g=1/FOPT^{1-\alpha}</math>. Then, the packing needs at most most <math>\mathrm{OPT} + \mathcal{O}(\logOPT^2 m\alpha)</math> bins, withand the run-time is in <math>O(T(mFOPT^{(1-\alpha)},n))</math>.

* At most <math>\mathrm{OPT} + \mathcal{O}(OPT^\alpha)</math> bins, with run-time in <math>O(T(FOPT^{(1-\alpha)},n))</math>, where <math>\alpha\in(0,1)</math> is a constant.

=== Algorithm 3 ===

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

*It Atuses at most <math>\mathrm{OPT} + \mathcal{O}(OPT\log^\alpha2 m)</math> bins, withand the run-time is in <math>O(T(FOPT^{(1-\alpha)}m,n))</math>, where <math>\alpha\in(0,1)</math> is a constant.

== Improvements ==