Online Bin Covering with Exact Parameter Advice

Andrej Brodnik, Bengt J. Nilsson, Gordana Vujovic

Abstract


We show an asymptotic 2/3-competitive strategy for the bin covering problem using O(b + log n) bits of advice, where b is the number of bits used to encode a rational value and n is the length of the input sequence.


Full Text:

PDF


DOI: https://doi.org/10.31449/inf.v48i4.4801

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.