时间：2025年11月21日（周五）9:30-10:30
地点：E4-233
主讲人: 朱玉，南方科技大学
讲座主题：Online Vector Bin Packing and Hypergraph Coloring Illuminated: Simpler Proofs and New Connections
讲座摘要: 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.
