Online Timely Bin Packing Revisited: A Simpler Algorithm with Optimality in Special Cases
Pei-Lin Chiang, Wing-Kai Hon, Ying-Chia Huang, Li-Tzu Yang
原文摘要
Online Timely Bin Packing is a variant of classical online bin packing in which items arrive over time with sizes and deadlines. Packing an item may be deferred until its deadline, but once a collection of items is packed into a bin, the bin is closed and cannot be used again. The objective is to minimize the total number of bins used. The problem was introduced by Khattar in 2023. In 2025, Aminian proposed Discrete-Greedy, a deterministic online algorithm with a competitive ratio of exactly $2$, which remains the best-known upper bound. Its analysis is particularly simple; however, the algorithm requires maintaining a fractional simulation internally and may leave usable space in some bins unfilled. We propose Thrifty-Greedy, a simple deterministic online algorithm that does not require a fractional simulation. We prove that its competitive ratio is exactly $2$, matching the best-known upper bound. At the same time, the algorithm automatically achieves the optimal competitive ratio on two natural classes of inputs: it is $1$-competitive when all items have the same size, and $1.5$-competitive when every item has size in $\{1/3,2/3\}$. In contrast, Discrete-Greedy has a competitive ratio of at least $2$ on both classes.
cs.DS