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, particularly for dimensions $d \ge 3$. The authors demonstrate that the previously known lower bound of $\Omega(d/\log^2 d)$ also holds in the asymptotic sense, a crucial finding for understanding the limits of online algorithms for this problem.

What Problem Does This Paper Address?

The paper tackles the problem of online vector bin packing (VP). In this scenario, we have a collection of $d$-dimensional vectors, each with components in $[0,1]$. The goal is to pack these vectors into the minimum number of bins, subject to the constraint that the sum of vector components in any bin does not exceed 1 in any dimension. The "online" aspect means that vectors arrive one by one, and each must be packed irrevocably before the next arrives.

A key challenge in analyzing online algorithms is understanding their performance guarantees. Two common measures are the absolute competitive ratio (worst-case performance over all possible inputs) and the asymptotic competitive ratio (worst-case performance for inputs where the optimal solution is large). While upper bounds for VP have often been studied in the asymptotic sense, lower bounds have lagged behind, especially for higher dimensions. Prior to this work, the best known lower bounds for the asymptotic competitive ratio were relatively weak (less than 3, even for large $d$). This paper aims to close this gap by providing much tighter asymptotic lower bounds.

Methods

The authors employ a variety of novel adaptive constructions to generate challenging input sequences for online algorithms. These constructions are designed to force the online algorithm to use many more bins than an optimal offline algorithm.

Key methodological aspects include:

  • Adaptive Constructions: This technique involves defining input items based on the algorithm's past actions. The properties of an item (e.g., whether it's "large" or "small") are determined by how the algorithm packs it. This allows for the creation of inputs that exploit specific weaknesses of online algorithms.
  • Multiple Phases: The constructions often involve distinct "phases," each designed to challenge the algorithm in a specific way. For instance, some phases might introduce items that are difficult to pack together, while others might focus on exploiting the algorithm's bin usage.
  • Careful Construction of Item Properties: The paper meticulously defines the components of the vectors, often using parameters like $\varepsilon$ and $\mu$ to create precise relationships between item sizes and bin capacities. These relationships are crucial for proving the lower bounds.
  • Adaptation of Coloring Problems: For their main result, the authors adapt constructions from online graph coloring problems, moving beyond simple "black-box" reductions to achieve tighter bounds for the asymptotic competitive ratio.

Datasets

Not discussed in the paper. The paper focuses on theoretical lower bounds and constructs adversarial input sequences rather than evaluating algorithms on existing datasets.

Key Insights and Ideas

  • Asymptotic vs. Absolute Bounds: The paper highlights the distinction between absolute and asymptotic competitive ratios and shows that strong asymptotic lower bounds can be achieved even when absolute bounds might be weaker.
  • Power of Adaptive Constructions: The adaptive construction method proves to be a powerful tool for generating challenging inputs that expose the limitations of online algorithms, leading to significantly improved lower bounds.
  • Dimensionality Matters: The paper demonstrates how the dimension $d$ significantly impacts the achievable competitive ratio, with new bounds derived for $d \ge 3$.
  • Bridging Coloring and Bin Packing: The adaptation of techniques from online coloring to vector bin packing is a novel approach that yields stronger results for the asymptotic competitive ratio.
  • $\Omega(d/\log^2 d)$ Holds Asymptotically: The most significant finding is that the previously known lower bound of $\Omega(d/\log^2 d)$ for the absolute competitive ratio also holds for the asymptotic competitive ratio, a substantial improvement over prior results.

Key Results

  • Improved Lower Bounds for $d \ge 3$: The paper provides significantly improved lower bounds on the asymptotic competitive ratio for online vector bin packing for all fixed dimensions $d \ge 3$.
  • Main Result: $\Omega(d/\log^2 d)$ Asymptotic Lower Bound: The paper proves that the asymptotic competitive ratio for online vector bin packing is at least $\Omega(d/\log^2 d)$. This matches the known absolute lower bound and is a major theoretical advancement.
  • $\Omega(\sqrt{d})$ Lower Bound: An adaptive construction yields a lower bound of $\Omega(\sqrt{d})$, which is particularly effective for medium-sized dimensions.
  • Specific Bounds for Small Dimensions: The paper derives specific lower bounds for small dimensions, such as $\approx 2.62$ for $d=8$ and $2.25$ for $d=3$.
  • Bounds for Large $d$: For very large $d$, a lower bound of $\Omega((\log^2 d)^3)$ is shown, and for sufficiently large fixed $d$, a bound of $\Omega(1/\log^2 d)^2$ is established.

Limitations and Future Work

  • Constant Factors: While the paper establishes the order of growth for lower bounds, the hidden constants in the $\Omega$ notation can be large, especially for the $\Omega(d/\log^2 d)$ bound. The authors suggest that their $\Omega(\sqrt{d})$ construction might offer better practical performance for medium dimensions due to smaller constants.
  • Randomized Algorithms: The paper mentions that the main result holds against randomized algorithms, but a more detailed analysis of randomized lower bounds for specific dimensions might be an area for future work.
  • Exact Values: The paper provides lower bounds, but the exact values of the best possible asymptotic competitive ratios (ASYM(d)) remain unknown for most dimensions. Determining these exact values is a long-standing open problem.
  • Further Exploration of Adaptive Constructions: The success of adaptive constructions suggests that further exploration of this technique could lead to even tighter bounds or insights into other online packing problems.

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},
}
Figure