Improving Online Bin Covering with Little Advice

The online bin covering problem is: given an input sequence of items find a placement of the items in the maximum number of bins such that the sum of the items’ sizes in each bin is at least~1. Boyar~{\em et~al}.@~\cite{boyar2021} present a strategy that with $O(\log \log n)$ bits of advice, where $n$ is the length of the input sequence, achieves a competitive ratio of $8\mathrm{/}15\approx 0.5333\dots$. We show that with a strengthened analysis and some minor improvements, the same strategy achieves the significantly improved competitive ratio of~$135\mathrm{/}242\approx 0.5578\dots$, still using $O(\log \log n)$ bits of advice.