跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

In online bin packing with delay, items of sizes in (0,1](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 22 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; bb fair bits suffice for ratio 2+2−b2+2^{-b}. A fixed threshold gives deterministic ratio 1+31+\sqrt3. The lower bounds 22 and e/(e−1)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/23/2, a deterministic polynomial 22-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/34/3.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 (0,1](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 22 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; bb fair bits suffice for ratio 2+2−b2+2^{-b}. A fixed threshold gives deterministic ratio 1+31+\sqrt3. The lower bounds 22 and e/(e−1)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/23/2, a deterministic polynomial 22-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/34/3.

查看此版本解读 →查看此版本原文 ↗