← 研踪 PaperTrailarXiv:2609.29589 · v2
Online Bin Packing with Per-Bin Maximum Delay
首次提交 2026-08-27 21:50
版本更新 2026-11-19 17:47
雷达观测 2026-11-20 19:57
摘要
In online bin packing with delay, items of sizes in 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 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; fair bits suffice for ratio . A fixed threshold gives deterministic ratio . The lower bounds and 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 , a deterministic polynomial -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 .
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-19 17:47 · 最新观测版本
Online Bin Packing with Per-Bin Maximum Delay
In online bin packing with delay, items of sizes in 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 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; fair bits suffice for ratio . A fixed threshold gives deterministic ratio . The lower bounds and 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 , a deterministic polynomial -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 .
查看此版本解读 →查看此版本原文 ↗