Online bin covering with advice

Joan Boyar, Lene M. Favrholdt, Shahin Kamali*, Kim S. Larsen

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

53 Downloads (Pure)

Abstract

The bin covering problem asks for covering a maximum number of bins with an online sequence of n items of different sizes in the range (0, 1]; a bin is said to be covered if it receives items of total size at least 1. We study this problem in the advice setting and provide tight bounds for the size of advice required to achieve optimal solutions. Moreover, we show that any algorithm with advice of size o(log log n) has a competitive ratio of at most 0.5. In other words, advice of size o(log log n) is useless for improving the competitive ratio of 0.5, attainable by an online algorithm without advice. This result highlights a difference between the bin covering and the bin packing problems in the advice model: for the bin packing problem, there are several algorithms with advice of constant size that outperform online algorithms without advice. Furthermore, we show that advice of size O(log log n) is sufficient to achieve a competitive ratio that is arbitrarily close to 0.53 3 ¯ and hence strictly better than the best ratio 0.5 attainable by purely online algorithms. The technicalities involved in introducing and analyzing this algorithm are quite different from the existing results for the bin packing problem and confirm the different nature of these two problems. Finally, we show that a linear number of bits of advice is necessary to achieve any competitive ratio better than 15/16 for the online bin covering problem.

Original languageEnglish
Title of host publicationAlgorithms and Data Structures : 16th International Symposium, WADS 2019, Proceedings
EditorsZachary Friggstad, Jörg-Rüdiger Sack, Mohammad R. Salavatipour
PublisherSpringer
Publication date12. Jul 2019
Pages225-238
ISBN (Print)978-3-030-24765-2
ISBN (Electronic)978-3-030-24766-9
DOIs
Publication statusPublished - 12. Jul 2019
Event16th International Symposium on Algorithms and Data Structures, WADS 2019 - Edmonton, Canada
Duration: 5. Aug 20197. Aug 2019

Conference

Conference16th International Symposium on Algorithms and Data Structures, WADS 2019
Country/TerritoryCanada
CityEdmonton
Period05/08/201907/08/2019
SponsorElsevier, PIMS Institute, Springer, University of Alberta
SeriesLecture Notes in Computer Science
Volume11646
ISSN0302-9743

Fingerprint

Dive into the research topics of 'Online bin covering with advice'. Together they form a unique fingerprint.

Cite this