# Online Bin Covering with Frequency Predictions

arXiv: https://arxiv.org/abs/2401.14881 · HTML: https://mlsanity.com/paper/2401.14881/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jan 2024.

## Built on by (most cited first, 1 of 1)

- [Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management](https://mlsanity.com/paper/2604.26349/) (2026)

## Abstract (arXiv)

We study the discrete bin covering problem where a multiset of items from a fixed set S subseteq (0,1] must be split into disjoint subsets while maximizing the number of subsets whose contents sum to at least 1. We study the online discrete variant, where S is finite, and items arrive sequentially. In the purely online setting, we show that the competitive ratios of best deterministic (and randomized) algorithms converge to frac12 for large S, similar to the continuous setting. Therefore, we consider the problem under the prediction setting, where algorithms may access a vector of frequencies predicting the frequency of items of each size in the instance. In this setting, we introduce a family of online algorithms that perform near-optimally when the predictions are correct. Further, we introduce a second family of more robust algorithms that presents a tradeoff between the performance guarantees when the predictions are perfect and when predictions are adversarial. Finally, we consider a stochastic setting where items are drawn independently from any fixed but unknown distribution of S. Using results from the PAC-learnability of probabilities in discrete distributions, we also introduce a purely online algorithm whose average-case performance is near-optimal with high probability for all finite sets S and all distributions of S.