PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Bin Packing with Per-Bin Maximum Delay

Tianhang Lu, Runtian Ren, Shengcai Liu

arXiv:2609.29589v1cs.DS

TL;DR

Existing bin-packing-with-delay models charge waiting additively per item, whereas this setting charges once per bin according to its oldest item and also imposes capacity constraints. The paper derives a temporal-span partition formulation, designs adversarial online algorithms, and analyzes Poisson arrivals with half-capacity items as an exact stochastic benchmark. The results include strong NP-hardness, no absolute approximation ratio below 3/2 unless P = NP, a polynomial 5(2 + √2)/6-approximation, and, under the ideal random-real convention, a polynomial Capacity-Overflow Random-Silence algorithm with expected ratio (3e−4)/(e−1) ≈2.418023.

  • Problem

    Existing bin-packing-with-delay models charge waiting additively per item, whereas this setting charges once per bin according to its oldest item and also imposes capacity constraints.

    Source: §1 · p. 1

  • Method

    The paper derives a temporal-span partition formulation, designs adversarial online algorithms, and analyzes Poisson arrivals with half-capacity items as an exact stochastic benchmark.

    Source: §1 · p. 2

  • Results

    The results include strong NP-hardness, no absolute approximation ratio below 3/2 unless P = NP, a polynomial 5(2 + √2)/6-approximation, and, under the ideal random-real convention, a polynomial Capacity-Overflow Random-Silence algorithm with expected ratio (3e−4)/(e−1) ≈2.418023.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The paper supplies exact algorithms for several special cases and an exact causal-policy benchmark for Poisson arrivals with half-capacity items, whose limiting ratio is at most 4/3.

    Source: §1 · p. 2

Abstract

from arXiv · show

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.

1 Introduction

The paper studies capacity-constrained online batching when each bin’s delay charge is set by its oldest item, rather than summed across items. It develops offline structure, adversarial algorithms, and a Poisson benchmark for this objective.

1 Introduction

  • The objective charges once per bin for service and for the oldest item's delay, so younger compatible items add no waiting charge.This differs from prior bin-packing-with-delay models that charge waiting additively over items.Source: §1 · p. 1

Adversarial online algorithms and the cost of capacity

  • A global random threshold and one Next-Fit buffer address capacity and waiting together; silence clusters provide negative credit against fragmentation.The threshold is sampled with density ex/(e −1), and the temporal cost for a fixed threshold matches uncapacitated random-silence batching.Source: §1 · p. 2

Offline geometry and approximation

  • The offline problem is strongly NP-hard and has no absolute approximation ratio below 3/2 unless P = NP; a polynomial 5(2 + √2)/6 ≈ 2.845-approximation is given.Exact algorithms are also reported for equal sizes, nonbinding capacity, and bin cardinality at most two.Source: §1 · pp. 2–3

Adversarial online algorithms and the cost of capacity

  • (3e−4)/(e−1) ≈ 2.418023 is the expected ratio of the polynomial Capacity-Overflow Random-Silence algorithm against an oblivious adversary in the ideal random-real model.The analysis couples Next-Fit fragmentation with negative credit from silence clusters.Source: §1 · p. 2

An exact binding-capacity benchmark

  • For rate-λ Poisson arrivals with item sizes 1/2, the paper gives the exact offline rate, an optimal causal policy, and a maximum limiting ratio of 4/3 for two asymptotic ratio notions.The ratio of expectations and conditional expected ratio have the same limit.Source: §1 · p. 2

B. Adversarial online competitiveness

The adversarial analysis compares strict competitive guarantees and treats randomized guarantees against an oblivious adversary. It uses the nonbinding-capacity case as a baseline for capacity-constrained results.

B. Adversarial online competitiveness

  • The adversarial results are organized as strict competitive comparisons, with randomized guarantees measured against an oblivious adversary.Table 1 separates these from offline approximation and long-run stochastic rates.Source: Table 1 · p. 3, B. Adversarial online competitiveness · p. 3
  • When capacity never binds, the problem is exactly per-batch maximum-delay TCP; Greedy has deterministic factor two, and the paper gives a self-contained exact randomized frontier for this class.The constant e/(e −1) is classical in randomized online batching.Source: B. Adversarial online competitiveness · p. 3
  • The paper’s roadmap assigns a randomized upper bound and a deterministic polynomial-time guarantee to the adversarial analysis.The randomized upper bound is developed in Section 5 and the deterministic guarantee in Section 6.Source: B. Adversarial online competitiveness · p. 3

2 Model and Preliminaries

The model represents each item by its size and arrival time, and permits sealed-bin service actions on pending items. It distinguishes deterministic and randomized competitive guarantees and states the computational conventions used for polynomial-time claims.

2 Model and Preliminaries

  • An input is a finite collection of distinct item occurrences with sizes in (0, 1] and nonnegative arrival times; equal sizes and arrival times are allowed.All items at an epoch are revealed before any action at that epoch.Source: §2 · p. 4
  • At a service epoch, an action selects a nonempty set of pending items for a fresh bin, subject to unit capacity, and seals that bin.The complete arrival epoch is revealed before the sequence of service actions begins.Source: §2 · p. 4
  • Every item must eventually be packed, and the input provides no end-of-input notification.The empty input has zero online and offline cost.Source: §2 · p. 4
  • For randomized guarantees, the input is fixed independently of the algorithm’s seed; continuous-threshold polynomial-time claims use an ideal random-real model.That model treats exact sampling, real arithmetic, and real comparisons as unit-cost operations; bit-model implementation requires a separate finite-precision or lazy-sampling statement.Source: §2 · p. 4
  • Randomized policies are required to be measurable and pathwise admissible, with policy transformations applied seed by seed.Expectations are taken after the transformed executions and their joint measurability have been established.Source: §2 · p. 4

3 Offline Temporal-Span Bin Packing

The offline objective admits a partition formulation using each bin’s temporal span. This structure yields gap-based decomposition, complexity and approximation results, and exact algorithms for several special cases.

3 Offline Temporal-Span Bin Packing

  • An offline optimum can seal each bin at the last arrival among its assigned items, yielding a static partition formulation.Moving service back to that arrival preserves feasibility and weakly decreases the maximum delay.Source: §3 · p. 5
  • Splitting bins at an arrival gap of length at least one does not increase cost, and the decomposition is sharp at equality.No optimum crosses a gap greater than one.Source: §3 · p. 5

3.1 Complexity and approximation

  • Simultaneous arrivals reduce the objective to ordinary bin packing, giving strong NP-hardness and ruling out absolute ratios below 3/2 unless P = NP.The result follows from simultaneous-arrival reductions based on 3-Partition.Source: §3.1 · p. 5

3.2 Exact special cases

  • Exact algorithms cover total size at most one, equal item sizes, instances with no feasible three-item bin, and arbitrary instances.Equal sizes admit an O(n log n) total-time algorithm after sorting; the no-three-item case is maximum-weight matching, and the arbitrary-instance subset dynamic program takes O(3^n) time and O(2^n) space.Source: §3.2 · p. 6

4 The Exact Temporal Baseline and General Lower Bounds

When capacity is nonbinding, the paper establishes exact deterministic and randomized competitive frontiers, then uses the randomized threshold rule as a baseline for the capacity-constrained model. It also gives lower bounds inherited by the full model.

4 The Exact Temporal Baseline and General Lower Bounds

  • Oldest-trigger normalization converts any policy into one that clears all pending items whenever it acts, without increasing cost when total size is at most one.For randomized policies, the guarantee holds pathwise for each fixed seed.Source: §4 · p. 6
  • Every deterministic algorithm has ratio at least two on the nonbinding class, and a nonresetting unit timer achieves 2-competitiveness there.The timer starts when the system becomes nonempty and clears all pending items when it fires.Source: §4 · pp. 6–7
  • Theorem 4.3 gives every randomized algorithm a competitive ratio of at least e/(e −1), even when total item size is at most one.A matching threshold-based upper bound makes this the exact randomized ratio on the nonbinding class.Source: §4 · p. 7

5 Random Silence with Binding Capacity

The section combines a global silence threshold with a single Next-Fit buffer, sealing on silence or capacity overflow. Its analysis couples temporal costs to capacity fragmentation through a negative credit from silence clusters.

5 Random Silence with Binding Capacity

  • A single global threshold X drives one Next-Fit buffer, whose timer resets after fitting arrivals and which seals on X units of silence or a nonfitting arrival.The threshold is sampled with density ex/(e −1).Source: §5 · p. 7

5.1 The uncapacitated gap identity

  • For the uncapacitated gap identity, the threshold rule expresses temporal cost through expected contributions from consecutive arrival gaps.The supplied derivation distinguishes gaps up to one from gaps of at least one.Source: §5.1 · p. 8

5.2 A pathwise capacity decomposition

  • Within each silence cluster, Next Fit’s buffer closures split into overflows and a temporal cluster cost, while silence cuts fragment offline bins across temporal-hull gaps.Counting those fragments yields HX, which also upper-bounds packing demand within the silence clusters.Source: §5.2 · p. 9, Figure 3 · p. 9

5.3 The signed silence potential

  • Capacity-Overflow Random Silence is strictly competitive in expectation against every oblivious adversary.The proof couples the Next-Fit fragment bound with a two-unit subtraction per silence cluster, rather than bounding temporal cost and overflows separately.Source: §5.3 · p. 10

6 A Deterministic Polynomial Baseline

Half-Full-or-One is a deterministic polynomial-time policy that seals bins on a half-full threshold or an age-one timer. Its proved guarantee is four-competitive, though the analysis is not tight.

6 A Deterministic Polynomial Baseline

  • The policy keeps a buffer below load 1/2, seals it when it reaches 1/2, and seals any remaining buffer when its oldest item reaches age one.Items of size at least 1/2 are sealed immediately, together with the pending buffer if they fit.Source: §6 · p. 10
  • Half-Full-or-One is strictly 4-competitive.Arrival-triggered bins have load at least 1/2, while timer bins have delay one; the analysis bounds total cost by 2V + 2D ≤ 4 OPT.Source: §6 · p. 10
  • Three compatible small items can make the ratio tend to three, and no factor-three proof is known for this algorithm.The authors report that exact searches have not found a larger ratio.Source: §6 · p. 10

7 Periodic Phase Decompositions

Periodic phase decomposition replaces online service decisions with capacity-feasible phase packing, exposing a trade-off between phase length and fragmentation. The section also gives a polynomial reduction for weighted phase packing and a lower barrier for two random-boundary families.

7 Periodic Phase Decompositions

  • The exact phase algorithm packs each phase’s items to minimize cost and seals its bins at the phase endpoint, but this optimization is strongly NP-hard.Placing all items at the endpoint recovers ordinary bin packing.Source: §7 · p. 11
  • Exact phase optimization has an exact supremal ratio whose two branches are 2 + L and 1 + 1/L.The branches arise respectively from two fragments near a boundary and from many crossed phases.Source: §7 · p. 11
  • A uniformly shifted grid has an expected fragment-cost bound with branches 1 + L/2 and 1 + 1/L.The two branches are both necessary for this algorithm, and finite inputs approach each one.Source: §7 · pp. 11–12
  • Neither global-random-period nor stationary-renewal boundaries improve the uniform shifted grid; the renewal result is a universal lower barrier, not an exact ratio for every renewal law.Arbitrary nonstationary or nonrenewal input-independent point processes are outside the stated coverage.Source: §7 · p. 12

7.1 Polynomial weighted phase packing

  • A layer-cake reduction turns weighted phase packing into prefix bin-packing bounds; using the absolute 5/3 ordinary online algorithm yields polynomial global ratios.Prefix consistency connects the number of bins meeting each age threshold to the ordinary packing bound.Source: §7.1 · p. 12

8 A Weighted Endpoint AFPTAS for the Phase Oracle

The section gives an AFPTAS for fixed-length weighted endpoint packing, closing the phase oracle despite the local problem’s strong NP-hardness. Its age-ordered construction uses nested residual-capacity constraints and controlled rounding, but its per-phase additive term does not by itself yield a polynomial-time online competitive ratio.

8 A Weighted Endpoint AFPTAS for the Phase Oracle

  • For every fixed rational L and ε, weighted endpoint packing admits a polynomial-time (1 + ε)-approximation with an additive term polynomial in L and 1/ε.The approximation is for the finite weighted subproblem; its per-phase additive term does not automatically yield a polynomial-time global online competitive guarantee.Source: §8 · p. 13, §8.4 · p. 16

8.1 Rounding ages and large sizes

  • Rounding ages to O(L/τ + 1) levels and grouping large items yields only O(K/τ^2) retained large-item types.Within each level, later size groups round upward into the preceding groups’ slots, while removed first-group items are packed as singletons.Source: §8.1 · p. 13

8.2 Configurations and nested residual capacity

  • The configuration LP imposes suffix constraints because older small items can use only bins declared at their age level or higher.The nested eligibility structure makes the highest-age demand’s neighborhood smallest.Source: §8.2 · p. 14

8.3 Integral reconstruction of small items

  • Small-item reconstruction discards at most one residual smaller than τ per template bin, keeping total overflow volume below τM.Next Fit then packs the overflow in nonincreasing age order, so each new bin’s first item is its oldest.Source: §8.3 · p. 15

8.4 Polynomial pricing

  • A knapsack FPTAS supplies polynomial-time pricing, while exact feasibility preserves the suffix constraints used in reconstruction.The resulting additive cost terms are polynomial in 1/τ for fixed L; applying the scheme independently per phase does not absorb those terms into one global additive constant.Source: §8.4 · pp. 15–16

9 An Exact Binding-Capacity Benchmark: Poisson Half-Size Items

For Poisson arrivals with half-capacity items, the paper derives an exact offline benchmark and an optimal causal pair-or-timeout policy. The two asymptotic ratio notions agree, with their maximum of 4/3 at λ = 1.

9 An Exact Binding-Capacity Benchmark: Poisson Half-Size Items

  • For half-size Poisson arrivals, the exact binding-capacity benchmark is solved for offline and optimal causal rates without an end-of-input signal.A finite timer clears a final unmatched item; the model sets both costs to zero when there are no arrivals.Source: §9 · pp. 16–17

9.1 The offline matching process

  • An offline optimum exists using only adjacent arrival pairs, yielding a recurrence for the cost on the first i arrivals.The claim is existential: tied instances may also have nonadjacent optima.Source: §9.1 · p. 17

9.2 Pair immediately or use a timer

  • Random timers do not improve the causal calculation, and the optimal timeout regime switches at λ = 1.The best action is immediate sealing below rate one and a diverging timer above it.Source: §9.2 · p. 18

9.3 The two stochastic ratios

  • The optimal long-run stochastic ratio reaches 4/3 at λ = 1 and tends to one in both sparse and dense limits.Algorithm 3 is asymptotically optimal among admissible causal algorithms.Source: §9.3 · p. 19, Figure 5 · p. 20

10 Synthesis and Open Problems

The paper’s results frame open questions about whether capacity changes the optimal adversarial frontier and how far offline approximation can be improved. The Poisson half-size model is an exact benchmark, while broader size distributions remain future work.

Online frontier

  • Silence clusters both fragment offline bins and generate negative credit that offsets Next-Fit overflow, yielding a polynomial ideal-real randomized ratio of about 2.418023.The synthesis identifies this as the coupling behind the main online result.Source: §10 · p. 20

Open adversarial frontiers

  • It remains unknown whether binding capacity raises the optimal randomized ratio above e/(e −1), and the deterministic frontier also has unresolved gaps.The stated randomized alternatives are a binding-capacity lower bound above e/(e −1) or a general algorithm matching that temporal constant.Source: §10 · p. 20

Offline approximation

  • The temporal-span objective lacks a sharp approximation threshold or full AFPTAS; the fixed-phase endpoint AFPTAS has additive loss per occupied phase.That loss does not automatically yield polynomial-time global guarantees, and the paper leaves approximation below 5(2 + √2)/6 open.Source: §10 · p. 20

Stochastic benchmark

  • For Poisson arrivals with half-size items, the offline rate and optimal causal rate are characterized, and the two long-run ratio notions agree with worst value 4/3.The next distinct size alphabet, {1/3, 2/3}, breaks immediate-pair normalization and is left for future work.Source: §10 · pp. 20–21

A Deferred Proofs for Offline Structure and Phase Algorithms

The appendix establishes structural facts about offline temporal-span packing, derives hardness and approximation arguments, and gives exact algorithms for special cases. It also proves deterministic and randomized lower bounds for the nonbinding online frontier.

A.1 Gap decomposition

  • At a gap of length at least one, splitting a crossing bin does not increase cost; gaps greater than one force an optimum not to cross, while equality can be sharp.The split-cost change is at most 1 − gj; two compatible items at times zero and one cost two together or separately.Source: §A.1 · p. 21

A.2 Hardness and the absolute barrier

  • Zero-time arrivals reduce the objective to ordinary bin packing, proving strong NP-hardness; a ratio below 3/2 would decide Partition in polynomial time.The absolute barrier argument does not rule out an asymptotic scheme with an additive term.Source: §A.2 · p. 21

A.3 Derandomizing the offline shifted-grid approximation √

  • Enumerating one representative from each offset interval yields a normalized partition no costlier than the offset average, derandomizing the shifted-grid approximation.Phase membership and the resulting packing are constant between the O(n) arrival-time residues modulo L.Source: §A.3 · p. 21

A.4 Exact special cases

  • Exact special cases include nonbinding capacity, equal sizes, cardinality at most two, and arbitrary instances via an O(3^n) subset dynamic program.For nonbinding capacity, cuts are chosen independently at gaps greater than one; equal-size instances reduce to consecutive blocks, and the cardinality-two case is maximum-weight matching.Source: §A.4 · p. 22

B.1 Deterministic lower bound

  • For deterministic online policies, recursively chosen arrivals yield a fixed finite input with a lower-bound ratio tending to two.The construction releases the next item just after the policy’s hypothetical service time for the current item.Source: §B.1 · pp. 22–23

B.2 Finite-support randomized lower bound

  • For randomized policies against an oblivious adversary, finite-support inputs give a lower-bound ratio tending to e/(e −1).The limits are taken first in K and then in m.Source: §B.2 · p. 23

C Approximate Pricing and Exact Column Recovery

These passages combine an exact-recovery argument for approximate pricing with stochastic results for half-size Poisson arrivals and a computational framework. They cover matching, policy normalization, rate bounds, timers, realized ratios, and finite-grid verification.

C Approximate Pricing and Exact Column Recovery

  • Approximate normalized pricing, exact rational ellipsoid feasibility, and restricted-LP recovery produce a basic feasible solution with at most m positive columns and polynomial encoding length.The recovered value is bounded by LP/(1 − ρ), where LP is the full optimum.Source: C Approximate Pricing and Exact Column… · pp. 24–25

D.1 Adjacent matching and the offline rate

  • The adjacent-matching recursion has a stationary saving increment with expectation λ/[2(1 + λ)], yielding the offline rate through an ergodic argument.A gap of at least one resets the recursion independently of the past.Source: §D.1 · p. 25

D.2 Policy-level immediate-pair normalization

  • Any causal half-size policy can be transformed into a canonical immediate-pair policy with pathwise cost no greater than the original.The repair acts causally and iterates until no pair opportunity is violated.Source: §D.2 · p. 26

D.3 Universal drift lower bound

  • The passage lists λ for λ ≤ 1 and (λ + 1)/2 for λ ≥ 1, but does not identify these expressions here as lower bounds.Source: §D.3 · p. 27

D.4 Increasing timers and terminal cleanup

  • For λ > 1, timers τk = (2/λ) log(k + 1) support the dense-regime construction; for λ ≤ 1, the zero timer gives the result directly.The timer sequence is horizon-free, and every timer is finite on a finite input.Source: §D.4 · pp. 27–28

D.5 Uniform integrability of the realized ratio

  • Uniform integrability upgrades convergence of the sample ratio to conditional expectation, while separate L1 cost-rate limits yield the ratio of expectations.The proof uses a pathwise envelope for the algorithm-to-optimum ratio.Source: §D.5 · p. 28

E Exact Computation and Falsification Framework

  • The finite-grid framework rounds virtual services with at most one added cost per bin and rejects oldest-frontier rules with examples approaching ratios 5/2 and 8/3.The quantitative transfer gives a factor of at most 1 + 1/D; the finite-game method avoids giving the online policy an end signal.Source: E Exact Computation and Falsification… · pp. 28–29

Disclosure of AI-Assisted Research and Writing

  • The authors report substantive AI-assistant use in proof exploration, counterexample search, formalization, literature organization, drafting, and revision; human authors verified the arguments and take responsibility.Source: Disclosure of AI-Assisted Research and… · p. 29
Loading 2609.29589v1…