Skip to content
Preprint

Online Bin Packing with Per-Bin Maximum Delay

Aug 2026 · 0 citations · 14 references
Computer Science

TL;DR

This work proves strong NP-hardness and rule out absolute approximation factors below three halves unless P equals NP, and obtains an exact stochastic benchmark for Poisson arrivals when every item has half the bin capacity.

Abstract

We study online bin packing with per-bin maximum delay: each sealed bin incurs a unit opening cost plus the longest waiting time among its items. Offline, this becomes a temporal-span packing objective. We prove strong NP-hardness and rule out absolute approximation factors below three halves unless P equals NP. We complement these barriers with a polynomial constant-factor approximation, exact algorithms for several special cases, and an AFPTAS for the fixed-length weighted endpoint subproblem. For adversarial online inputs, we give an efficient randomized algorithm in the ideal random-real model with expected competitive ratio about 2.418 against an oblivious adversary, together with deterministic and randomized lower bounds. Its analysis couples Next-Fit fragmentation to a negative credit generated by silence clusters. Both frontiers are solved exactly when capacity is nonbinding. We also obtain an exact stochastic benchmark for Poisson arrivals when every item has half the bin capacity: we characterize the offline rate, identify an optimal causal policy, and show that two natural asymptotic ratio notions agree and are bounded by four thirds.

View source

Similar papers

Sep 2026

Online Covering with Maximum Delay under Subadditive Service Costs

Online covering in which each instantaneous service pays its purchase cost and one maximum waiting time, with no effect on future requests is studied, finding an offline consecutive-batch normal form that transfers static approximation guarantees to the offline problem.

Tian-Han Lu, Run-Tian Ren, Sheng-Cai Liu · 1 citation
Preprint Sep 2026

Online Matching in Convex Bipartite Graphs

Online resource-allocation systems, like outpatient scheduling and spectrum allocation, often assign sequentially arriving requests to an ordered pool of scarce resources, where each request accepts a contiguous interval of feasible options. We study the resulting online matching problem on convex bipartite graphs unde...

Yi-Long Feng, Zhihao Gavin Tang, Kang-Ning Wang et al. · 0 citations
Preprint Sep 2026

Improved Upper Bounds for Dynamic Bin Packing of General, Unit-Fraction, and Power-Fraction Squares

This paper presents significant upper-bound improvements for dynamic 2D square bin packing, where square items arrive and depart over time and the objective is to minimize the peak number of concurrent active unit bins. In our model, repacking is permitted only within a destination bin upon item arrival; migration betw...

Miguel A. Mini, F. Miyazawa, Gabriela M. Silva et al. · 0 citations
Preprint Sep 2026

Single-or-Sample: Online Fair Allocation for Combinatorial Agents

A new randomized online algorithm for additive and submodular valuations, called Single-or-Sample, is developed, that achieves a constant-factor approximation to MMS simultaneously for all agents, with constant probability, and establishes a fundamental tradeoff between approximation and success probability.

Shuchi Chawla, Zhi-Yi Huang, Pooja Kulkarni et al. · 1 citation
Preprint Aug 2026

Online Service with Per-Batch Maximum Delay

This work uses spatial blindness---announced requests whose locations are revealed only when visited---as a stress test: dyadic exploration preserves a constant ratio on a known finite line, while a single hidden request on a star forces a loss linear in its degree.

Tian-Han Lu, Run-Tian Ren, Sheng-Cai Liu et al. · 0 citations
Sep 2026

Online Stochastic Allocation with Increasing Returns

We study online allocation with increasing returns, where an uncertain number of customers arrive sequentially and can be irrevocably assigned to any product with remaining capacity. Each assignment earns a base reward plus a bonus that is nondecreasing in the number of previous assignments to the same product. Prior w...

Shuo Sun, Yun-Duan Lin · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.