2026-08-13T13:22:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20050 2024-05-31T13:11:11Z ddc:004 open_access

Online Bin Covering with Frequency Predictions Berg, Magnus Kamali, Shahin Bin Covering Online Algorithms with Predictions PAC Learning Learning-Augmented Algorithms We study the bin covering problem where a multiset of items from a fixed set S ⊆ (0,1] must be split into disjoint subsets while maximizing the number of subsets whose contents sum to at least 1. We focus on 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 1/2 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 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Magnus Berg and Shahin Kamali 2024 Is Part Of LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2024.10 urn:nbn:de:0030-drops-200504 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.10 eng https://creativecommons.org/licenses/by/4.0/legalcode