Truly Asymptotic Lower Bounds for Online Vector Bin Packing

János Balogh, Ilan Reuven Cohen, Leah Epstein, Asaf Levin

TL;DR

This paper establishes new, significantly stronger lower bounds for the asymptotic competitive ratio of online vector bin packing algorithms. The authors prove that for any dimension $d \ge 3$, the best possible asymptotic competitive ratio is at least $\Omega(d/\log^2 d)$, matching the known upper bound and resolving a long-standing open question.

What Problem Does This Paper Address?

The paper tackles the online vector bin packing (VP) problem. In VP, items are $d$-dimensional vectors with components in $[0,1]$, and the goal is to pack them into bins such that the sum of components in each bin does not exceed 1 for any dimension. The "online" aspect means items arrive one by one and must be packed without knowledge of future items. The "asymptotic competitive ratio" measures how well an algorithm performs compared to an optimal offline solution as the total number of bins used by the optimal solution grows infinitely large. While upper bounds for VP were known, lower bounds, especially for the asymptotic measure, were relatively weak, particularly for higher dimensions. This paper aims to close this gap by providing much tighter lower bounds.

Methods

The authors employ a variety of constructions to derive their lower bounds. A key technique is the use of "adaptive constructions," where the properties of incoming items are dynamically defined based on the algorithm's actions. This allows for the creation of challenging instances that exploit the online nature of the problem. For higher dimensions, they adapt ideas from previous work on online graph coloring and use a fractional coloring approach. The proofs often involve carefully analyzing the number of bins used by the online algorithm versus an optimal offline packing, leveraging properties of the constructed item sequences. They also introduce specific constructions for different ranges of dimensions ($d \ge 3$, medium-sized $d$, and specific small dimensions like $d=3$ and $d=8$) to achieve the tightest possible bounds.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and proofs rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Matching Upper and Lower Bounds: The paper's most significant contribution is proving a lower bound of $\Omega(d/\log^2 d)$ for the asymptotic competitive ratio, which matches the best known upper bound. This resolves a major open question about the inherent difficulty of online vector bin packing.
  • Power of Adaptive Constructions: The paper demonstrates the effectiveness of adaptive constructions in generating challenging instances for online algorithms, leading to significantly improved lower bounds.
  • Dimensionality Matters: The results highlight how the dimension $d$ fundamentally impacts the complexity of online vector bin packing, with lower bounds growing with $d$.
  • Distinction Between Absolute and Asymptotic Ratios: The authors emphasize that lower bounds for the absolute competitive ratio do not directly translate to the asymptotic case, necessitating specialized constructions for the latter.

Key Results

The paper establishes the following key lower bounds on the asymptotic competitive ratio for online vector bin packing:

  • For $d \ge 3$, a lower bound of $\Omega(d/\log^2 d)$ is proven, matching the best known upper bound.
  • For very large $d$, a lower bound of $\Omega(\log^2 d / d^3)$ is shown.
  • For sufficiently large and fixed $d$, a lower bound of $\Omega(1/(\log^2 d)^2)$ is achieved.
  • For a wide range of $d$, a lower bound of $\Omega(\sqrt{d})$ is derived using adaptive constructions.
  • Specific lower bounds are derived for smaller dimensions:
  • $d=3$: $\Omega(2.25)$
    • $d=8$: $\Omega(\approx 2.62)$

Limitations and Future Work

The paper focuses on theoretical lower bounds and does not present empirical results. While the paper provides tight asymptotic lower bounds, the exact values of the best possible asymptotic competitive ratios for specific dimensions remain an open area. The authors suggest that further exploration of adaptive constructions and their application to other online packing problems could yield additional insights. The paper also mentions that their constructions are "truly asymptotic," meaning they hold even when the optimal solution uses an arbitrarily large number of bins.

Summary updated

Abstract

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.
BibTeX
@inproceedings{balogh2021truly,
  author = {János Balogh and Ilan Reuven Cohen and Leah Epstein and Asaf Levin},
  title = {{Truly Asymptotic Lower Bounds for Online Vector Bin Packing}},
  booktitle = {APPROX-RANDOM},
  year = {2021},
  doi = {10.4230/lipics.approx/random.2021.8},
}

Loading related content...

Figure