(click to copy)


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 𝑂(log⁡log⁡𝑛) bits of advice, where n is the length of the input sequence, achieves a competitive ratio of 8/15≈0.5333…. We show that with a strengthened analysis and some minor improvements, the same strategy achieves the significantly improved competitive ratio of 135/242≈0.5578…, still using 𝑂(log⁡log⁡𝑛) bits of advice.

A. Brodnik, J.B. Nilsson, G. Vujovic, Improving Online Bin Covering with Little Advice, In: A.A. Rescigno, U. Vaccaro (eds), Combinatorial Algorithms: IWOCA 2024, Lecture Notes in Computer Science 14764 (2024), Springer.

Gordana Vujovic © private

Gordana Vujović

0 Pages 0 Press 0 News 0 Events 0 Projects 0 Publications 0 Person 0 Visualisation 0 Art


CSH Newsletter

Choose your preference
Data Protection*