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 et al. [3] 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/15\approx 0.5333\ldots \) . We show that with a strengthened analysis and some minor improvements, the same strategy achieves the significantly improved competitive ratio of  \(135/242\approx 0.5578\ldots \) , still using \(O(\log \log n)\) bits of advice.