REVIEW 3 minor 14 references
Asymptotic optimality of dynamic first-fit packing on the half-axis
T0 review · 0 major / 3 minor · reviewed 2026-05-24 · grok-4.3
Pith's one-line read First-fit dynamic packing converges to a gap-free size-ordered configuration as arrival rate tends to infinity
desk verdict This paper gives the first proof of the 1985 conjecture on asymptotic optimality of first-fit for non-degenerate countable-support H. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The first-fit placement rule, which assigns each item to the leftmost feasible gap, together with the convergence in distribution of the scaled configuration to the deterministic sorted no-gap limit
What would settle it
Finding a countable-support distribution H where for large r the scaled empty space remains positive with positive probability would falsify the claim
Extended reading notes
Core claim
Under the first-fit discipline, as r tends towards infinity, the steady-state packing configuration (scaled down by r) converges in distribution to the limiting packing configuration with smaller items on the left, larger items on the right, and with no gaps between. In particular, this proves asymptotic optimality of first-fit in the sense that in steady-state the empty space (scaled down by r) vanishes.
Load-bearing premise
The distribution H of item sizes is supported on a countable increasing sequence of positive reals, finite or unbounded, with finite mean
Editorial extensions
If this is right
- The ratio of expected empty space to expected occupied space tends to zero
- The limiting configuration has all items packed contiguously in increasing size order from the origin
- Asymptotic optimality holds for the specified class of item size distributions H
- The result resolves the conjecture of Coffman, Kadota, and Shepp for non-degenerate H with countable support
Reading between the lines
- The size-ordering may indicate that first-fit achieves the optimal packing density in the fluid limit
- The proof technique might extend to distributions with continuous support though the paper restricts to countable cases
- Other online algorithms could be benchmarked against this same limiting configuration
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves asymptotic optimality of the first-fit discipline for dynamic storage allocation on the half-axis. Items arrive as a Poisson process of rate r with i.i.d. sizes from H (supported on a countable increasing sequence of positive reals, finite or infinite, with finite mean) and depart after unit-mean exponential times. The main result states that the r-scaled steady-state configuration under first-fit converges in distribution to the deterministic gap-free packing with items ordered by increasing size from left to right; as a corollary the scaled empty space vanishes.
Significance. The result resolves the 1985 conjecture of Coffman, Kadota and Shepp for non-degenerate H, extending their unit-size case. If the technical arguments hold, the work supplies the first rigorous proof of convergence in distribution to the ordered gap-free limit under a natural topology, thereby establishing asymptotic optimality via continuity of the empty-space functional. The countable-support assumption is explicitly scoped and the derivation is parameter-free.
minor comments (3)
- The abstract states the convergence claim and the required conditions on H, but the full derivation steps, technical lemmas, and handling of the continuous-time Markov process are not available for inspection in the provided excerpt; the central claim therefore cannot be verified from given text.
- Clarify the precise topology on the space of configurations under which convergence in distribution is proved (e.g., vague convergence on the half-axis or a suitable Skorokhod space) and confirm that the empty-space functional is continuous at the limit point.
- The statement that H is 'concentrated on countably many positive real sizes forming an increasing sequence' should be accompanied by an explicit definition of the support sequence (a_n) and the finite-mean condition in the main theorem statement.
Simulated Author's Rebuttal
We thank the referee for their positive summary, significance assessment, and recommendation of minor revision. No major comments appear in the report, so we have no points requiring point-by-point response or manuscript changes.
Circularity Check
No significant circularity; derivation self-contained
full rationale
The paper establishes convergence in distribution of the r-scaled steady-state first-fit configuration to an externally described deterministic limit (smaller items left, larger right, gap-free) for H supported on countable increasing sizes with finite mean. This limit is not defined via the result itself, nor obtained by fitting parameters or self-citation chains. The asymptotic optimality claim (vanishing scaled empty space) follows from continuity of the empty-space functional at the limit point. No load-bearing step reduces to a self-definition, fitted input renamed as prediction, or ansatz smuggled via prior self-work. The derivation is independent of the target claim and externally falsifiable under the stated assumptions.
Assumptions & free parameters
assumptions (3)
- domain assumption Items arrive according to a Poisson process of rate r
- domain assumption Service times are i.i.d. exponential with unit mean
- domain assumption Item sizes are i.i.d. from H supported on a countable increasing sequence of positive reals with finite mean
Cite this review
Pith. "Pith review of Asymptotic optimality of dynamic first-fit packing on the half-axis." pith.science (2026). https://pith.science/paper/NPSF6WYE
@misc{pith2026240403797,
author = {Pith},
title = {Pith review of: Asymptotic optimality of dynamic first-fit packing on the half-axis},
year = {2026},
howpublished = {\url{https://pith.science/paper/NPSF6WYE}},
note = {Machine review of arXiv:2404.03797}
}
abstract
We revisit a classical problem in dynamic storage allocation. Items arrive in a linear storage medium, modeled as a half-axis, at a Poisson rate $r$ and depart after an independent exponentially distributed unit mean service time. The arriving item sizes (lengths) are assumed to be independent and identically distributed (i.i.d.) from a common distribution $H$. A widely employed algorithm for allocating the items is the "first-fit" discipline, namely, each arriving item is placed in the left-most vacant interval large enough to accommodate it. In a seminal 1985 paper, Coffman, Kadota, and Shepp ([6]) proved that in the special case of unit length items (i.e. degenerate $H$), as $r$ tends towards infinity, the first-fit algorithm is asymptotically optimal in the following sense: the steady-state ratio of expected "empty space" (gaps between items) to expected occupied space tends towards $0$. In a sequel to [6], Coffman, Kadota, and Shepp ([5]) conjectured that the first-fit discipline is also asymptotically optimal for non-degenerate $H$. In this paper we provide the first proof of first-fit asymptotic optimality for non-degenerate distributions $H$ of item sizes. Our main result is for the case when $H$ is concentrated on countably many positive real sizes forming an increasing sequence that is either finite or goes to infinity, with the average item size being finite. We prove that under the first-fit discipline, as $r$ tends towards infinity, the steady-state packing configuration (scaled down by $r$) converges in distribution to the limiting packing configuration with smaller items on the left, larger items on the right, and with no gaps between. In particular, this proves asymptotic optimality of first-fit in the sense that in steady-state the empty space (scaled down by $r$) vanishes.
Figures
Reference graph
Works this paper leans on
-
[1]
Aldous, D. (1986). Some interesting processes arising as heavy traffic limits in an M/M/ ∞ storage process. Stochastic Processes and their Applications , 22(2), 291–313
work page 1986
-
[2]
Coffman, E.G., Flatto, L., and Leighton, F.T. (1990). First-fit allocation of queues: tight probabilistic bounds on wasted space. Stochastic Processes and their Applications , 36(2), 311–330
work page 1990
-
[3]
Coffman, E.G., Flatto, L., and Leighton, F.T. (1990). First-fit storage of linear lists: tight probabilis- tic bounds on wasted space. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 272–279)
work page 1990
-
[4]
Coffman, E.G., Kadota, T.T., Leighton, F.T., and Shepp, L.A. (1986). Stochastic analysis of storage fragmentation. In Teletraffic Analysis and Computer Performance Evaluation (pp. 275–295)
work page 1986
-
[5]
Coffman, E.G., Kadota, T.T., and Shepp, L.A. (1985). On the asymptotic optimality of first-fit storage allocation. IEEE Transactions on Software Engineering , 11(2), 235–239
work page 1985
-
[6]
Coffman, E.G., Kadota, T.T., and Shepp, L.A. (1985). A stochastic model of fragmentation in dynamic storage allocation. SIAM Journal of Computing , 14(2), 416–425
work page 1985
-
[7]
Coffman, E.G. and Leighton, F.T. (1986). A provably efficient algorithm for dynamic storage allocation. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (pp. 77–90)
work page 1986
-
[8]
Knessl, C. (2000). Asymptotic expansions for a stochastic model of queue storage. The Annals of Applied Probability, 10(2), 592–615
work page 2000
Show all 14 references
-
[9]
Knessl, C. (2004). Some asymptotic results for the M/M/ ∞ queue with ranked servers. Queueing Sys- tems, 47, 201–250
2004
-
[10]
and Lee, M.K
Park, B.C. and Lee, M.K. (2007). Closest open location rule under stochastic demand. International Journal of Production Research, 45(7), 1695–1705
2007
-
[11]
and Knessl, C
Sohn, E. and Knessl, C. (2010). Storage allocation under processor sharing I: exact solutions and asymptotics. Queueing Systems, 65(1), 1–18
2010
-
[12]
and Knessl, C
Sohn, E. and Knessl, C. (2011). Storage allocation under processor sharing II: further asymptotic results. European Journal of Applied Mathematics , 22(1), 45–82
2011
-
[13]
and Knessl, C
Sohn, E. and Knessl, C. (2011). On some simple single server models of dynamic storage. In Proceedings of the 6th International Conference on Queueing Theory and Network Applications (pp. 161–168)
2011
-
[14]
and Knessl, C
Sohn, E. and Knessl, C. (2012). Some exact and asymptotic solutions to single server models of dynamic storage. Stochastic Models, 28(2), 248–280. 11
2012
Reviewed May 24, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.