Content deleted Content added
Added tags to the page using Page Curation (refimprove, more footnotes) |
m Open access bot: doi added to citation with #oabot. |
||
Line 217:
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 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.
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|doi-access=free}}</ref> use a similar scheme in which the items are first packed into "containers", and then the containers are packed into bins. Their algorithm needs at most <math>b_J \leq OPT(I) + O(\log(OPT))</math> bins.
== References ==
| |||