2026-08-17T16:22:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14701 2024-03-06T10:54:41Z ddc:004 open_access

Truly Asymptotic Lower Bounds for Online Vector Bin Packing Balogh, János Cohen, Ilan Reuven Epstein, Leah Levin, Asaf Bin packing online algorithms approximation algorithms vector packing In this work, we consider online d-dimensional vector bin packing. It is known that no algorithm can have a competitive ratio of o(d/log² d) in the absolute sense, although upper bounds for this problem have always been presented in the asymptotic sense. Since variants of bin packing are traditionally studied with respect to the asymptotic measure, and since the two measures are different, we focus on the asymptotic measure and prove new lower bounds of the asymptotic competitive ratio. The existing lower bounds prior to this work were known to be smaller than 3, even for very large d. Here, we significantly improved on the best known lower bounds of the asymptotic competitive ratio (and as a byproduct, on the absolute competitive ratio) for online vector packing of vectors with d ≥ 3 dimensions, for every dimension d. To obtain these results, we use several different constructions, one of which is an adaptive construction with a lower bound of Ω(√d). Our main result is that the lower bound of Ω(d/log² d) on the competitive ratio holds also in the asymptotic sense. This result holds also against randomized algorithms, and requires a careful adaptation of constructions for online coloring, rather than simple black-box reductions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik János Balogh and Ilan Reuven Cohen and Leah Epstein and Asaf Levin 2021 Is Part Of LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2021.8 urn:nbn:de:0030-drops-147013 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.8 eng https://creativecommons.org/licenses/by/4.0/legalcode