Truly asymptotic lower bounds for online vector bin packing

• 成果类型: Article; Early Access
• 署名作者: Balogh, Janos; Cohen, Ilan Reuven; Epstein, Leah; Levin, Asaf
• 署名单位: Szeged University; Bar Ilan University; University of Haifa; Technion Israel Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02276-3
• 发表日期: 2025
• 关键词: algorithms

摘要

In this work, we consider online d-dimensional vector bin packing. For this problem, it is known that no algorithm can have a competitive ratio of o(d/log2d)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$o(d/\log <^>2 d)$$\end{document} in the absolute sense, although upper bounds for it are typically presented in the asymptotic sense. Since variants of bin packing are traditionally studied with respect to the asymptotic measure, and since the two measures are different, we focus on the asymptotic measure, and prove new lower bounds on the asymptotic competitive ratio. The existing lower bounds (on the asymptotic competitive ratio) known prior to this work were smaller than 3, even for very large values of d. Here, we significantly improve the best known lower bounds on the asymptotic competitive ratio (and as a byproduct, on the absolute competitive ratio) for online vector packing of vectors with d >= 3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d \ge 3$$\end{document} dimensions, for every dimension d. To obtain these results, we use several different constructions, one of which is an adaptive construction showing a lower bound of Omega(d)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega (\sqrt{d})$$\end{document} on the asymptotic competitive ratio. Our main result is that the lower bound of Omega(d/log2d)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega (d/\log <^>2 d)$$\end{document} on the competitive ratio holds also in the asymptotic sense. This result holds also against randomized algorithms, and requires a careful adaptation of constructions for online coloring, rather than simple black-box reductions.