{"id":"43586799-9b84-427f-832b-03c8ab0ea216","arxiv_id":"2404.03797","paper_version":2,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":8.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"First proof that dynamic first-fit packing on the half-axis is asymptotically optimal for non-degenerate countable-support item size distributions, with scaled steady-state configuration converging to gap-free size-ordered packing as arrival rate r tends to infinity.","lead":"The paper proves that first-fit packing of items with varying sizes on a half-axis becomes asymptotically optimal as arrival rate grows large, for item sizes from certain countable distributions. A smart generalist might read it to see how simple allocation rules perform without waste in high-load systems.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"Reader correctly extracted the countable-support restriction as the explicit scope of the result rather than a hidden flaw. The logic from distributional convergence to vanishing empty space is standard once continuity or integrability is verified, and nothing in the given claim description indicates that step is missing or incorrect.","tokens_in":1884,"tokens_out":240,"duration_ms":22317,"concrete_test":"Confirm that the topology on configurations makes the total scaled empty space a continuous functional at the limit packing, or that the paper supplies uniform integrability of the empty-space random variables.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is explicitly scoped to H supported on a countable increasing sequence of sizes (finite or infinite) with finite mean. The stated result is convergence in distribution of the r-scaled steady-state configuration to the deterministic gap-free sorted packing; the 'in particular' claim that scaled empty space vanishes follows if the empty-space functional is continuous at the limit point under the topology of convergence in distribution. No internal inconsistency, unjustified step, or unsupported assumption is visible from the abstract and claim description.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","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.","tokens_in":1977,"tokens_out":410,"duration_ms":13522,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"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.","responses":[],"tokens_in":1390,"tokens_out":59,"duration_ms":8511,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main point is that the authors close the Coffman-Kadota-Shepp conjecture for item sizes with countable support. They show that under first-fit, the r-scaled steady-state configuration converges in distribution to the deterministic gap-free packing with smaller items left and larger right. This implies the scaled empty space vanishes as r goes to infinity.","headline":"This paper gives the first proof of the 1985 conjecture on asymptotic optimality of first-fit for non-degenerate countable-support H.","tokens_in":2441,"tokens_out":141,"would_cite":false,"duration_ms":11239,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[],"headline":"Stochastic first-fit packing optimality via Markov drift has no RS connection","alignment":"orthogonal","rationale":"The paper proves hydrodynamic convergence of a first-fit storage process (Poisson arrivals, exp departures, two item sizes) to a gap-free sorted configuration using generator drift arguments on empty-space and hole-count Lyapunov functions (Propositions 3.1–3.4, Lemmas 3.5–3.6). This machinery is standard countable-state Markov process analysis and has zero overlap with RS primitives (distinction forcing, J-cost functional equation, φ-ladder, 8-tick periodicity). No ratio-symmetric cost, no recognition ladder, no parameter-free constant derivation appears. The result is therefore orthogonal to the RS framework.","tokens_in":48879,"confidence":"high","tokens_out":172,"duration_ms":4716,"cache_read_input_tokens":38528,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"First-fit dynamic packing converges to a gap-free size-ordered configuration as arrival rate tends to infinity","keywords":["first-fit packing","dynamic storage allocation","asymptotic optimality","Poisson arrivals","steady-state convergence","half-axis model","item size distribution"],"falsifier":"Finding a countable-support distribution H where for large r the scaled empty space remains positive with positive probability would falsify the claim","tokens_in":2789,"feed_emoji":"📦","tokens_out":617,"duration_ms":23210,"temperature":0.7,"pith_summary":"This paper establishes the asymptotic optimality of the first-fit algorithm for dynamic item placement on a half-axis when item sizes come from a distribution with countable support. Items arrive according to a Poisson process with rate r and have exponentially distributed service times. The key result shows that the steady-state configuration, scaled by 1/r, converges in distribution to one where items are arranged from smallest to largest with no empty space between them. This implies that the proportion of wasted space goes to zero as r becomes large. The proof covers distributions concentrated on countably many sizes that are either finite in number or increase to infinity, with finite average size.","feed_headline":"First-fit packing empties gaps at high arrival rates","feed_subtitle":"Scaled configuration converges to size-ordered no-gap limit for countable item sizes, proving empty space vanishes","key_machinery":"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","core_discovery":"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.","pith_inferences":["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"],"forward_implications":["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"],"fun_headline_variants":["First-fit achieves no-gap limit for countable sizes at high r","Dynamic first-fit packing converges to size-ordered configuration","As r to infinity first-fit empty space scaled by r vanishes","First-fit on half-axis is asymptotically optimal for countable H"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The distribution H of item sizes is supported on a countable increasing sequence of positive reals, finite or unbounded, with finite mean","fun_headline_variants_meta":{"raw":{"variants":["First-fit achieves no-gap limit for countable sizes at high r","Dynamic first-fit packing converges to size-ordered configuration","As r to infinity first-fit empty space scaled by r vanishes","First-fit on half-axis is asymptotically optimal for countable H"]},"model":"grok-4.3","cost_usd":0.005025,"raw_usage":{"total_tokens":2516,"prompt_tokens":797,"num_sources_used":0,"completion_tokens":65,"cost_in_usd_ticks":50249500,"prompt_tokens_details":{"text_tokens":797,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1654,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":797,"tokens_out":65,"duration_ms":15538,"temperature":1.0,"reasoning_tokens":1654,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-24T01:58:33.595890+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Finding a countable-support distribution H where for large r the scaled empty space remains positive with positive probability would falsify the claim","supporting_citations":[],"review_version":1}