Online Bin Packing with Predictions
Journal of Artificial Intelligence Research · 20.12.2023 · 78 · 1111-1141
DOI: 10.1613/jair.1.14820 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Artificial Intelligence Research, online erschienen am 20.12.2023. Verfasst von Spyros Angelopoulos und 2 weiteren Autor:innen. Die Arbeit wurde bisher 15-mal zitiert (Crossref).
Abstract (Originalsprache)
Bin packing is a classic optimization problem with a wide range of applications, from load balancing to supply chain management. In this work, we study the online variant of the problem, in which a sequence of items of various sizes must be placed into a minimum number of bins of uniform capacity. The online algorithm is enhanced with a potentially erroneous prediction concerning the frequency of item sizes in the sequence. We design and analyze online algorithms with efficient tradeoffs between the consistency, which is the competitive ratio assuming no prediction error, and the robustness, which is the competitive ratio under adversarial error. Moreover, we demonstrate that the performance of our algorithm degrades near-optimally as a function of the prediction error. This is the first theoretical and experimental study of online bin packing under competitive analysis in the realistic setting of learnable predictions. Previous work addressed only extreme cases with respect to the prediction error and relied on overly powerful and error-free oracles.
Zitieren
APA
Angelopoulos, S., Kamali, S., & Shadkami, K. (2023). Online Bin Packing with Predictions. Journal of Artificial Intelligence Research, 78, 1111-1141. https://doi.org/10.1613/jair.1.14820
Vancouver
Angelopoulos S, Kamali S, Shadkami K. Online Bin Packing with Predictions. Journal of Artificial Intelligence Research. 2023;78:1111-1141. doi:10.1613/jair.1.14820
BibTeX
@article{Angelopoulos2023,
author = {Angelopoulos, Spyros and Kamali, Shahin and Shadkami, Kimia},
title = {Online Bin Packing with Predictions},
journal = {Journal of Artificial Intelligence Research},
year = {2023},
volume = {78},
pages = {1111--1141},
doi = {10.1613/jair.1.14820}
}
EUVIMED