Online Bin Packing with Per-Bin Maximum Delay
Tianhang Lu, Runtian Ren, Shengcai Liu
原文摘要
In online bin packing with delay, items of sizes in $(0,1]$ arrive over time and may wait before being packed into unit-capacity bins. A service selects a nonempty feasible batch of pending items and seals it in a new bin, at a service cost of one. We study the objective that adds one maximum waiting time for each sealed bin to the total service cost. Thus a bin's delay is determined by its oldest item, and younger items that fit can join it without increasing that delay. We give a randomized online algorithm with strict competitive ratio $2$ against an oblivious adversary, running in polynomial time in the ideal random-real model. It maintains one Next-Fit buffer and uses a single random silence threshold. Its analysis combines an offline-bin fragmentation bound with a two-unit saving per silence cluster. The ratio is tight for this policy; $b$ fair bits suffice for ratio $2+2^{-b}$. A fixed threshold gives deterministic ratio $1+\sqrt3$. The lower bounds $2$ and $e/(e-1)$ are attained when capacity is nonbinding. Offline, the problem minimizes the number of bins plus their total arrival span. We prove strong NP-hardness, an absolute approximation barrier of $3/2$, a deterministic polynomial $2$-approximation, and exact algorithms for several special cases. We also give stronger online ratios with exact endpoint-packing oracles and an AFPTAS for the fixed-length weighted endpoint subproblem. Finally, for Poisson arrivals of half-size items, we determine the offline and optimal causal long-run cost rates. Two natural asymptotic ratio measures coincide and have maximum $4/3$.
cs.DS