Content deleted Content added
Erel Segal (talk | contribs) added Category:Bin packing using HotCat |
Erel Segal (talk | contribs) No edit summary |
||
Line 37:
Now, we add the small items into the existing bins in an arbitrary order, as long as there is room. When there is no more room in the existing bins, we open a new bin (as in [[next-fit bin packing]]). Let <math>b_I</math> be the number of bins in the final packing. Then: <blockquote><math>b_I \leq \max(b_J, (1+2 g)\cdot OPT(I) + 1)</math>.</blockquote>''Proof''. If no new bins are opened, then the number of bins remains <math>b_J</math>. If a new bin is opened, then all bins except maybe the last one contain a total size of at least <math>B - g\cdot B</math>, so the total instance size is at least <math>(1-g)\cdot B\cdot (b_I-1)</math>. Therefore, <math>FOPT \geq (1-g)\cdot (b_I-1)</math>, so the optimal solution needs at least <math>(1-g)\cdot (b_I-1)</math> bins. So <math>b_I \leq OPT/(1-g) + 1 = (1+g+g^2+\ldots) OPT+1 \leq (1+2g) OPT+1</math>.
In particular, by taking ''g''=1/''n'', we get:<blockquote><math>b_I \leq \max(b_J, OPT +2 \cdot OPT(I)/n + 1)\leq \max(b_J, OPT +3)</math>,</blockquote>since <math>OPT(I)\leq n</math>. Therefore, it is common to assume that all items are larger than 1/''n''.<ref name=":2" />
== Step 2. Grouping and un-grouping items ==
Line 173 ⟶ 175:
*1-b. Add the items smaller than ''g'' to get a solution for <math>I</math>. The number of bins is: <math>b_I \leq \max(b_J, (1+2 g)\cdot OPT(I) + 1)\leq (1+\epsilon)OPT(I) + 1/2\epsilon^2 + 3</math>.
All in all, the number of bins is in <math>(1+\epsilon)OPT + O(\epsilon^{-2})</math> and the run-time is in <math>O(n\log n + T(\epsilon^{-2},n))</math>. By choosing <math>\epsilon = OPT^{-1/3}</math> we get <math>OPT + O(OPT^{2/3})</math>.
=== Algorithm 2 ===
Line 185 ⟶ 187:
***3-b. Round '''x''' to an integral solution for <math>K</math>. Do ''not'' add bins for the fractional part. Instead, just remove the packed items from <math>J</math>.
**2-b. Pack the items in ''<math>K'</math>'' in at most ''<math>2 k\cdot (2 + \ln(1/g))</math>'' bins.
*2. Once <math>FOPT(J) \leq 1+\frac{k}{k-1}\ln(1/g)</math>, pack the remaining items greedily into at most <math>2 FOPT(J) \leq 2+\frac{2 k}{k-1}\ln(1/g)</math> bins.
**At each iteration of the loop in step 2, the fractional part of '''x''' has at most ''m''(''K'') patterns, so <math>FOPT(J_{t+1}) \leq m(K_{t}) \leq FOPT(J_{t})/k + \ln(1/g)</math>. The FOPT drops by a factor of ''k'' in each iteration, so the number of iterations is at most <math>\frac{\ln FOPT(I)}{\ln k}+1</math>.
**Therefore, the total number of bins used for <math>J</math> is: <math>b_J \leq OPT(I) + \left[1+\frac{\ln FOPT(I)}{\ln k}\right]\left[1 + 4k + 2k\ln(1/g)\right]+ 2 + \frac{2k}{k-1}\ln(1/g)</math>.
*1-b. Add the items smaller than ''g'' to get a solution for <math>I</math>. The number of bins is: <math>b_I \leq \max(b_J, (1+2 g)\cdot OPT(I) + 1)</math>.
The run-time is in <math>O(n\log n + T(FOPT(J)/k + \ln(1/g),n))</math>.
Now, if we choose ''k''=2 and ''g''=1/FOPT(I), we get:<blockquote><math>b_J \leq OPT + O(\log^2(FOPT)) </math>, </blockquote>and
▲<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>O(n\log n) + T(FOPT/2 + \ln(FOPT) ,n)\in O(n\log{n} + T(FOPT, n)) </math>.
The same 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}(OPT^\alpha)</math> bins, and the run-time is in <math>O(n\log{n} + T(FOPT^{(1-\alpha)},n))</math>.
Line 209 ⟶ 211:
== Improvements ==
The KK techniques were improved later, to provide even better approximations.
The KK techniques were improved later, to provide even better approximations: an algorithm by Rothvoss<ref name=":2">{{Cite journal|last=Rothvoß|first=T.|date=2013-10-01|title=Approximating Bin Packing within O(log OPT * Log Log OPT) Bins|url=https://ieeexplore.ieee.org/document/6686137|journal=2013 IEEE 54th Annual Symposium on Foundations of Computer Science|volume=|pages=20–29|arxiv=1301.4010|doi=10.1109/FOCS.2013.11|isbn=978-0-7695-5135-7|via=|s2cid=15905063}}</ref> uses at most <math>\mathrm{OPT} + O(\log(\mathrm{OPT})\cdot \log\log(\mathrm{OPT}))</math>bins, and an algorithm by Hoberg and Rothvoss<ref name=":3">{{Citation|last1=Hoberg|first1=Rebecca|title=A Logarithmic Additive Integrality Gap for Bin Packing|date=2017-01-01|url=https://epubs.siam.org/doi/abs/10.1137/1.9781611974782.172|work=Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms|pages=2616–2625|series=Proceedings|publisher=Society for Industrial and Applied Mathematics|doi=10.1137/1.9781611974782.172|isbn=978-1-61197-478-2|access-date=2021-02-10|last2=Rothvoss|first2=Thomas|s2cid=1647463}}</ref> uses at most <math>\mathrm{OPT} + O(\log(\mathrm{OPT}))</math> bins.▼
Rothvoss<ref name=":2">{{Cite journal|last=Rothvoß|first=T.|date=2013-10-01|title=Approximating Bin Packing within O(log OPT * Log Log OPT) Bins|url=https://ieeexplore.ieee.org/document/6686137|journal=2013 IEEE 54th Annual Symposium on Foundations of Computer Science|volume=|pages=20–29|arxiv=1301.4010|doi=10.1109/FOCS.2013.11|isbn=978-0-7695-5135-7|via=|s2cid=15905063}}</ref> used the same scheme as Algorithm 2, but with a different rounding procedure in Step 2. He introduced a "gluing" step, in which small items are glued together to yield a single larger item. This gluing can be used to increase the smallest item size to about <math>B/\log^{12}(n)</math>. When all sizes are at least <math>B/\log^{12}(n)</math>, we can substitute <math>g = 1/\log^{12}(n)</math> in the guarantee of Algorithm 2, and get:<blockquote><math>b_J \leq OPT(I) + O(\log(FOPT)\log(\log(n)))</math>, </blockquote>which yields a <math>\mathrm{OPT} + O(\log(\mathrm{OPT})\cdot \log\log(\mathrm{OPT}))</math> bins.
▲
== References ==
| |||