Time：9:30-10:30, Friday, November 21 2025
Venue：E4-233
Speaker: Yu Zhu, Southern University of Science and Technology
Title：Online Vector Bin Packing and Hypergraph Coloring Illuminated: Simpler Proofs and New Connections
Abstract: In a breakthrough Azar et al (STOC'2013) proved a nearly tight lower bound of online vector bin packing problem (OVBP) by building a connection with online graph coloring. The proof was complicated and depended on intricate graph structures. We significantly simplified their proof by proposing a new connection with online hypergraph coloring (OHC). Our new proof is not only conceptually simple but also improved their bound. Azar et al also proved an upper bound of FirstFit algorithm for OVBP, their upper bound depends on the bin capacity. We use a simple double counting argument to improve their bound to a tight bound, removing the dependency on the bin capacity. Lastly, we prove a conjecture of Nagy-Gyorgy and Imreh (2008) about lower bound of online coloring hypertrees. The crux of this proof lies in solving a certain combinatorial partition problem about multi-family of subsets, which we also give a simple proof and might be of independent interest.
