2020/07/30 by Nikhil Bansal, Bansal, Nikhil, Ilan Reuven Cohen +1
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2007.15709
openalex publication_date 2020/07/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the online vector bin packing problem where n items specified by d-dimensional vectors must be packed in the fewest number of identical d-dimensional bins. Azar et al. (STOC'13) showed that for any online algorithm A, there exist instances I, such that A(I), the number of bins used by A to pack I, is Ω(d/log2 d) times OPT(I), the minimal number of bins to pack I. However in those instances, OPT(I) was only O(log d), which left open the possibility of improved algorithms with better asymptotic competitive ratio when OPT(I) ≫ d. We rule this out by showing that for any arbitrary function q(⋅) and any randomized online algorithm A, there exist instances I such that E[A(I)] ≥ c⋅ d/log3d ⋅ OPT(I) + q(d), for some universal constant c.