Online vector bin packing and hypergraph coloring illuminated: Simpler proofs and new connections

Abstract

This paper studies the online vector bin packing (OVBP) problem and the online hypergraph coloring (OHC) problem. Throughout the whole paper the matrix view plays an important part. Firstly, we introduce a notion of an online incidence matrix that is defined for every instance of OHC. Using this notion, we provide a simple reduction from OHC to OVBP, which allows us to carry known lower bounds of the competitive ratio of algorithms for OHC to OVBP. Our approach significantly simplifies the previous argument from Azar et al (2013) that relied on using intricate graph structures. Secondly, we use a double counting argument to prove upper bounds of the competitive ratio of F i r s t F i t for OVBP. The double counting is applied to estimate the sum of entries of all online vectors viewed as a matrix. Our proof is conceptually simple, and strengthens the result in Azar et al (2013) by removing the dependency on the bin size parameter. We also provide matching lower bounds for both the discrete and continuous cases. Lastly, we establish a tight bound on the competitive ratio of algorithms for OHC, where input is restricted to be a hypertree, thus resolving a conjecture by Nagy-György and Imreh (2008). The crux of this proof lies in solving a certain combinatorial partition problem about multi-family of subsets, which might be of independent interest.

The authors' abstract, as published at the source. Discrete Applied Mathematics, 2026 · DOI ↗