Online Bin Covering with Exact Parameter Advice

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.

References

Authors

  • Andrej Brodnik
  • Bengt J. Nilsson
  • Gordana Vujovic

DOI:

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

Downloads

Published

01/23/2025

Issue

Vol. 48 No. 4 (2024)

Section

MATCOS-22

License

Authors retain copyright in their work. By submitting to and publishing with Informatica, authors grant the publisher (Slovene Society Informatika) the non-exclusive right to publish, reproduce, and distribute the article and to identify itself as the original publisher.

All articles are published under the Creative Commons Attribution license CC BY 3.0. Under this license, others may share and adapt the work for any purpose, provided appropriate credit is given and changes (if any) are indicated.

Authors may deposit and share the submitted version, accepted manuscript, and published version, provided the original publication in Informatica is properly cited.

How to Cite

Online Bin Covering with Exact Parameter Advice. (2025). Informatica, 48(4). https://doi.org/10.31449/inf.v48i4.4801