Ilan Cohen on Lower Bounds for Online Vector Packing Problems via Graph Coloring

Apologies the first few minutes are missing.

In this talk, we will show tight lower bounds for the two major online vector packing problems, In both problems, the input consists of d-dimensional vectors, which we are required to pack into d-dimensional bins.

For the vector scheduling problem, the objective is to pack the d-dimensional vectors into a fixed set of bins and to minimize the maximum load of the bins (in any coordinate), we show a lower bound of \Omega(log d/ log log d). For the vector bin packing problem, where the objective is to pack the d-dimensional vectors into bins with a maximum load of 1 (in any coordinate) using a minimal number of bins, we show lower bound of \Omega(d^{1/B}), where 1/B is the maximum vector coordinate size, for a constant B. Both lower bounds are tight, given the upper bounds for these problems.

Our lower bounds rely on a reduction to variants of the online graph coloring problem. In the original problem, we are given an online realization of vertices and their previous neighbors, and the objective is to immediately and irrevocably color the vertices with a minimal number of colors such that no adjacent vertices have the same color. The first variant we consider, the online monochromatic clique problem, the objective is to color the vertices with a fixed set of colors and to minimize the largest monochromatic clique. The second variant we consider is the K-clique free coloring problem, where the goal is to color the graph with a minimal number of colors, such that each color class induces a K-clique free subgraph. We prove that these online graph coloring variants are hard and based on these we derive tight bound for the online vector packing problems.

Joint work with: Yossi Azar, Debmalya Panigrahi, Seny Kamara, Bruce Shepherd