Online Bin Covering with Advice.

Joan Boyar, Lene M. Favrholdt, Shahin Kamali, and Kim S. Larsen.
Algorithmica, 83(3): 795-821, 2021.

The bin covering problem asks for covering a maximum number of bins with an online sequence of n items of different sizes in the range (0,1]; a bin is said to be covered if it receives items of total size at least 1. We study this problem in the advice setting and provide asymptotically tight bounds of Theta(n log opt) on the size of advice required to achieve optimal solutions.

Moreover, we show that any algorithm with advice of size o(loglog n) has a competitive ratio of at most 0.5. In other words, advice of size o(loglog n) is useless for improving the competitive ratio of 0.5, attainable by an online algorithm without advice. This result highlights a difference between the bin covering and the bin packing problems in the advice model: for the bin packing problem, there are several algorithms with advice of constant size that outperform online algorithms without advice. Furthermore, we show that advice of size O(loglog n) is sufficient to achieve an asymptotic competitive ratio of 0.533333 which is strictly better than the best ratio 0.5 attainable by purely online algorithms. The technicalities involved in introducing and analyzing this algorithm are quite different from the existing results for the bin packing problem and confirm the different nature of these two problems.

Finally, we show that a linear number of advice bits is necessary to achieve any competitive ratio better than 15/16 for the online bin covering problem.

---

publication

Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any): The final publication is available at link.springer.com.

open access (378 KB)

The same as the publisher's version, when the publisher permits. Otherwise, the author's last version before the publisher's copyright; this is often exactly the same, but sometimes fonts, page numbers, figure numbers, etc. are different. It may also be a full version. However, it is safe to read this version, and at the same time cite the official version, as long as references to concrete locations, numbered theorems, etc. inside the article are avoided.

other publications

Other publications by the author.