{"id":"12c60629-a72d-4fce-98bd-455d0dca655b","arxiv_id":"2507.14812","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A black-box batching extension preserves the competitive ratio of any online resource allocation algorithm under exogenous replenishment, asymptotically when starting inventory is large, plus an impossibility result for large stochastic replenishments.","lead":"This paper gives a general \"batching\" trick that lets any online resource-allocation algorithm, designed for fixed inventory, handle exogenous replenishment while keeping its competitive ratio in the large-inventory regime. It covers both adversarial and stochastic arrivals, and shows a limit case where no such lossless extension is possible.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.2 is not proven as written: Lemma 4.2's rounding proof puts realized replenishment in the Chernoff mean bound where the LP only gives expected replenishment, so the OPT(H)≈LP(H) bridge for stochastic replenishment is unsupported.","rationale":"The reader's weakest assumption (the stochastic model is two-point and bounded, not 'arbitrary') is real: Theorem 2.3 itself shows M=Ω(c) is impossible, so the abstract overstates the scope. But the more load-bearing issue for the paper's formal claim is internal: in Theorem 2.2's proof, the lemma that approximates OPT(H) by LP(H) is only valid when replenishment is deterministic, because the randomized-rounding argument uses realized ζ in a capacity inequality where the LP feasibility condition gives expected q. This is not a mere overstatement of the abstract; it is a false step in the proof of the stochastic positive result. The LP comparison between HB and H is also one-sided as written. I do not recommend REJECT: the batching construction is elegant, the adversarial Theorem 2.1 and the impossibility Theorem 2.3 are substantially more secure, and the identified gap is concrete and plausibly fixable by adding a concentration event for ζ and a two-sided LP(HB) comparison. The CONDITIONAL verdict should stand, with the stochastic proof as the condition to repair.","tokens_in":21780,"tokens_out":17656,"duration_ms":217362,"concrete_test":"Re-derive Lemma 4.2 for a one-resource stochastic instance: c_i=c, m=2c requests of one type, each consuming one unit for reward 1, and ζ_i(j) i.i.d. two-point {0,1} with q=1/2 (M=1=o(c)). On the path with Σ_{t≤j}ζ_i(t)=0, check whether the proof's mean bound E[Σ A\\bar X] ≤ (c_i+Σζ)/(1+δ) holds; it fails because LP(H) only implies E ≤ (c+Σq)/(1+δ). Then repair the argument by adding the event Σζ ≥ (1−γ)Σq with a union bound and verify whether the extra loss is O(sqrt(log(cd)/c)) when M=o(c). If the repaired bound needs a factor exponential in M/c, Theorem 2.2's lossless claim fails; if the extra loss absorbs into ϵ, the proof can be fixed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4.2 (Theorem 2.2) needs the comparison OPT(HB)≈OPT(H) to transfer ALG's competitive ratio on HB back to H. The proof bridges OPT to the expected LP using Lemma 4.2, but that lemma is only proved for deterministic replenishment. In Appendix A.2, the rounding feasibility event is {Σ_tΣ_kΣ_z A_{itkz}(j)\\bar X_{tkz} ≤ c_i + Σ_{t≤j} ζ_i(t)}, and the Chernoff hypothesis is asserted as E[Σ A\\bar X] ≤ (c_i+Σ_{t≤j} ζ_i(t))/(1+δ). However, x* is feasible for LP(H), whose constraint (3) uses the right-hand side c_i+Σ_{t≤j} q_{it} (expected replenishment), not the realized ζ_i(t). On low-replenishment paths, e.g., Σ_{t≤j}ζ_i(t)=0, the asserted inequality is false; no conditioning or union bound over ζ is supplied. Hence the displayed exp(−δ²cmin/3) bound does not follow for stochastic replenishment, and the middle factor OPT(HB)/OPT(H) has no proved lower bound. The same subsection also derives only LP(HB) ≤ (1−ϵ)LP(H), whereas the final (1−O(ϵ)) factor requires a lower bound on LP(HB) that accounts for the additive ϵc batching slack. These are precise proof obligations; they may be repairable, but the lossless stochastic extension is not established as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes black-box 'batching' transformations that convert an online resource-allocation instance with exogenous replenishment into a fixed-inventory instance, so that any existing online algorithm ALG designed for the no-replenishment setting can be run on the transformed instance. For adversarial arrivals and adversarial replenishment, cumulative replenishment of each resource is batched until it reaches a threshold √cmin, new resource types are created for each batch, and the authors claim ALG's competitive ratio α(c) is preserved up to a 1−O(√(log(cd)/c)) factor. For stochastic arrivals and stochastic replenishment, the random replenishment is replaced by a discounted fluid process (1−ϵ)q, a batched instance is precomputed, and ALG is run on that virtual instance, with fallback to a trivial action when the realized inventory is insufficient; the claimed guarantee is α(O(M^{1/3} c^{2/3} log(cd))) (1−O(M^{1/3} c^{-1/3} log(cd))). The paper also proves an impossibility result (Theorem 2.3) showing that when a single replenishment can be as large as the starting inventory, no lossless transformation is possible. The analysis is structured in two steps: comparing ALG-B on the batched instance to ALG, and comparing the offline benchmarks OPT(HB) and OPT(H) through an expected-LP relaxation.","tokens_in":22098,"tokens_out":12604,"duration_ms":150342,"significance":"If the proofs are completed, the paper would provide a clean modular reduction that extends a large family of known online allocation algorithms to settings with exogenous replenishment, including Adwords, assortment optimization, hypergraph matching, and reusable-resource problems. The adversarial-replenishment result appears sound and is a genuine generalization of the batching idea from Feng et al. The stochastic-replenishment result, if repaired, would be the first general treatment of stochastic replenishment in this framework, and the impossibility result for large replenishments is a useful and convincing counterpoint. The paper is also transparent about the main limitations: the stochastic guarantee is conditional on bounded replenishments with M=o(cmin), and the impossibility for large replenishments is stated explicitly. The two-step LP-based proof structure is elegant and likely to be reusable. However, as written, the stochastic theorem has load-bearing proof gaps, so the advertised lossless stochastic extension is not yet established.","major_comments":[{"comment":"In the proof of Lemma 4.2, the randomized rounding scheme bounds the event {Σ_t Σ_k Σ_z A_{itkz}(j) \\bar X_{tkz} ≤ c_i + Σ_{t≤j} ζ_i(t)} by asserting E[Σ A \\bar X] ≤ (c_i + Σ_{t≤j} ζ_i(t))/(1+δ). However, the LP constraint (3) only gives E[Σ A \\bar X] ≤ (c_i + Σ_{t≤j} q_{it})/(1+δ). For a stochastic replenishment process, ζ_i(t) is random: on a low-replenishment path such as Σ ζ_i(t)=0, the asserted inequality is false, and no conditioning or union bound over the replenishment path is supplied. Consequently, the displayed exp(−δ² cmin/3) bound does not follow for stochastic replenishment, and the bridge OPT(HB)≈OPT(H) in Theorem 2.2 is unsupported.","section":"Appendix A.2, Lemma 4.2 (used in §4.2)"},{"comment":"The proof only derives the upper bound LP(HB) ≤ (1−ϵ)LP(H). The final displayed inequality multiplies by (1−ϵ) as though this gave a lower bound on OPT(HB)/OPT(H), but the chain actually requires both a lower bound LP(HB) ≥ (1−O(ϵ))LP(H) and an application of Lemma 4.2 to HB, whose minimum initial inventory is ϵcmin (worst case ϵc). That application would contribute a factor 1−O(√(log(ϵ cd)/(ϵ c))) = 1−O(ϵ^{−1/2} √(log(cd)/c)), which is not O(ϵ) in general. These proof obligations are not discharged, so the claimed factor α(ϵc)(1−O(ϵ)) does not follow as written.","section":"Section 4.2, comparison of LP(HB) and LP(H)"},{"comment":"The inequality ALG-B_j(H) ≥ P(Σ_{t≤j} ζ_i(t) ≥ Σ_{t≤j} ζ^B_i(t) for all i ∈ I_j) ALG_j(HB) treats cumulative replenishment dominance as sufficient for implementability of ALG's chosen action in the real instance. This requires an explicit coupling of the consumption random variables A between the virtual execution on HB and the real execution on H, together with an aggregate argument showing that actions using batched resource copies consume the same original resource in H. Neither is stated; without such a coupling, the event considered does not control realized consumption. This gap is likely repairable, but the lower bound on ALG-B(H)/ALG(HB) is not fully justified as written.","section":"Section 4.2, first inequality for ALG-B_j(H)"}],"minor_comments":[{"comment":"The abstract's phrase 'arbitrary (adversarial or stochastic) replenishment process' is stronger than the model: in Section 2, stochastic replenishment is assumed to be a family of independent two-point random variables with a uniform upper bound M, and Theorem 2.2 is conditional on M=o(cmin). The abstract and Table 1 should be reworded to reflect this condition.","section":"Abstract and Section 2"},{"comment":"The definition of ϵ in Algorithm 2 uses cmin, whereas the probability calculation and Theorem 2.2 use c; the paper should state explicitly that c is a lower bound on cmin and replace cmin by c, or introduce cB=ϵc consistently.","section":"Algorithm 2 and Section 4.2"},{"comment":"The lower bound LP(HB) ≥ (1−1/√c)LP(H) is asserted without proof. It follows by scaling an optimal LP(H) solution by (1−1/√c) and using ci ≥ c, but the argument should be written out, especially because the analogous stochastic lower bound is one of the missing pieces.","section":"Section 4.1"},{"comment":"The choice δ = √(3 log(cd)/c) can exceed 1 for small values of c, while Lemma A.1 requires δ ∈ (0,1]; since all results are asymptotic in the large-inventory regime, this restriction should be stated explicitly.","section":"Appendix A.2, Lemma 4.2"},{"comment":"After deriving the upper bound (1+γ)c on the expected online reward, the text says the maximum expected reward 'is 2c'; this appears to be a typo for (1+γ)c, since the subsequent competitive-ratio expression (2+2γ)/(2+3γ) uses (1+γ)/(1+1.5γ).","section":"Section 4.3, proof of Theorem 2.3"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know before reading: the adversarial-arrivals half (Theorem 2.1) is in good shape, and the stochastic-arrivals half (Theorem 2.2) has a load-bearing proof gap the writeup does not close. This is a case where the high-level idea is better than the current proof of it.\n\nWhat's actually new. A black-box batching transformation: accumulate replenishment until it reaches a threshold, then introduce it as a new \"virtual\" resource type, so any algorithm in the Devanur et al. framework runs on a fixed-inventory instance. That generalizes Feng et al.'s batching from the IB algorithm to arbitrary algorithms, which is a real extension. The stochastic-arrival-with-replenishment results are new, and the impossibility result (Theorem 2.3) is both new and correct — I checked the hard instance and the (2+2γ)/(2+3γ) ratio; the argument goes through. The two-step analysis is clean and unifies adwords, assortment, hypergraph matching, and reusable resources. The adversarial part is solid: the LP comparisons there are true, just under-proved.\n\nWhat's soft. The stress-test note is right about Lemma 4.2. The rounding proof in the appendix puts realized replenishment ζ_i(t) in the Chernoff threshold, but the LP constraint it cites only gives expected replenishment q_i(t). On low-replenishment paths (say all ζ = 0, which has positive probability), the asserted bound E[ΣAX̄] ≤ (c_i+Σζ)/(1+δ) is false, and no conditioning or union bound over ζ supplies it. Theorem 2.2 leans on this lemma for the OPT(HB) ≈ OPT(H) bridge, so the lossless stochastic extension is not established as written. It looks repairable — condition on the high-replenishment event and absorb the probability — but it's a genuine proof obligation.\n\nSection 4.2 also states the LP comparison in the wrong direction: \"implying LP(HB) ≤ (1-ε)LP(H)\" is followed by a chain that needs a lower bound. The lower bound is actually true — scaling any LP(H) solution by (1-ε) is feasible for LP(HB); the same scaling proves the asserted (1-1/√c) factor in Section 4.1. So both LP comparisons are fixable in a few lines, but as written they're gaps. The abstract oversells \"arbitrary stochastic replenishment process\" when the model is independent two-point variables bounded by M = o(c); the body qualifies this, so that's a presentational fix. Minor: the Chernoff bound cited in Section 4.2 is an upper-tail lemma doing lower-tail duty, and the Theorem 2.3 proof has a small typo (\"maximum expected reward is 2c\" should be (1+γ)c).\n\nWho it's for. Researchers in online resource allocation who want a general tool to lift no-replenishment results into replenishment settings. The deterministic part is usable now; the stochastic part is worth citing for the reduction idea and the impossibility boundary, not yet for the guarantee as stated.\n\nRecommendation: send it to review. It's a serious paper with specific, identifiable gaps; a competent referee can force the repairs, and the finished product is worth having. My verdict matches the reader's: conditional.","headline":"The batching reduction is a genuinely useful black-box idea and the impossibility result holds up, but Theorem 2.2 is not proven as written; the stochastic half needs a real repair, not copyediting.","tokens_in":22675,"tokens_out":17383,"would_cite":true,"duration_ms":174450,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","68W40","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Batching lets online allocation algorithms keep their competitive-ratio guarantees when inventory is exogenously replenished, so long as the starting inventory is large.","keywords":["online resource allocation","exogenous replenishment","competitive ratio","black-box transformation","batching extension","adversarial arrivals","stochastic arrivals","large inventory regime"],"falsifier":"Run $\\mathrm{ALG\\text{-}B}$ on a family of stochastic instances with $M=o(c)$ where each replenishment is an independent two-point variable, and compare its average reward with the offline value on the same realizations; if the ratio falls below $\\alpha(O(M^{1/3}c^{2/3}\\log(cd)))(1-O(M^{1/3}c^{-1/3}\\log(cd)))$ by a non-vanishing amount, the stochastic theorem's constants are wrong. For the adversarial theorem, an instance in which replenishment arrives one unit per period while the threshold is $\\sqrt{c}$ would expose whether the delay loss is actually bounded by the claimed $O(\\sqrt{\\log(cd)/c})$ factor. The explicit $G_S$ instance in Section 4.3 is a built-in falsifier for any claim that the lossless regime extends to $M=\\Omega(c)$: any online algorithm there has expected reward at most $(1+\\gamma)c$ against an offline value of $(1+3\\gamma/2)c$.","tokens_in":21529,"feed_emoji":"📦","tokens_out":11279,"duration_ms":113827,"temperature":0.7,"pith_summary":"The paper's central claim is a recipe for adding exogenous replenishment to online resource allocation without redesigning algorithms. In the model, resources start with inventories $c_i$, requests arrive online, and each request also brings replenishment $\\zeta_i(j)$ of every resource; the question is whether an algorithm $\\mathrm{ALG}$ designed for the no-replenishment case can be extended, in a black-box way, to this replenished case while keeping its competitive ratio. The answer it tries to establish is yes in the large-inventory regime, via batching: hold replenished inventory until it reaches a threshold $c_B$, then feed the accumulated amount to the original algorithm as a new resource type introduced at time zero. For adversarial arrivals the preserved ratio is $\\alpha(\\sqrt{c})(1-O(\\sqrt{\\log(cd)/c}))$; for stochastic arrivals and bounded stochastic replenishment it is $\\alpha(O(M^{1/3}c^{2/3}\\log(cd)))(1-O(M^{1/3}c^{-1/3}\\log(cd)))$; and when replenishment can be as large as the initial inventory, the paper proves no lossless extension exists in general.","feed_headline":"Batched inventory refills preserve online allocation ratios","feed_subtitle":"Black-box batching lets fixed-inventory online algorithms handle replenished resources with vanishing loss.","key_machinery":"The central object is the batching extension, a threshold-based transformation of the replenishment stream. For each resource, $\\mathrm{ALG\\text{-}B}$ accumulates incoming inventory and only releases it as a new resource type once the accumulated amount reaches $c_B$; that batched amount then acts as the starting inventory of a copy of the resource treated as having been available from the beginning, with duplicated actions carrying the same rewards. The paper sets $c_B=\\sqrt{c_{\\min}}$ for adversarial replenishment and $c_B=\\epsilon c_{\\min}$ with $\\epsilon=(3M\\log(cd)/c)^{1/3}$ for stochastic replenishment. For stochastic arrivals the algorithm precomputes a deterministic fluid batched instance from $(1-\\epsilon)q_{ij}$, runs the original algorithm on that instance virtually, and falls back to the trivial action only when realized inventory is insufficient, while updating the virtual state as if the chosen action succeeded; the concentration bound $P(\\sum_{t\\le j}\\zeta_i(t)<\\sum_{t\\le j}\\zeta_i^B(t))\\le 1/(cd)$ controls the fallback probability. The analysis then separates into a comparison between $\\mathrm{ALG\\text{-}B}(H)$ and $\\mathrm{ALG}(H_B)$, which inherits the original competitive ratio $\\alpha(c_B)$, and a comparison between the LP relaxations of $H_B$ and $H$, which bounds the loss from batching.","core_discovery":"On the paper's own terms, the discovery is that exogenous replenishment can be factored out of online resource allocation in the large-inventory regime. Given any algorithm $\\mathrm{ALG}$ with parametric competitive ratio $\\alpha(c)$ on instances without replenishment, the paper constructs a batching extension $\\mathrm{ALG\\text{-}B}$ that converts a replenished instance into a no-replenishment instance $H_B$ whose minimum starting inventory is the batching threshold, and shows the conversion is asymptotically lossless: Theorem 2.1 gives the adversarial-arrival bound, Theorem 2.2 gives the stochastic bound when $M=o(c)$, and the impossibility result Theorem 2.3 draws the boundary at $M=\\Omega(c)$. The argument rests on two comparisons: the batching algorithm's reward equals, or in the stochastic case is within a $1-1/c$ factor of, the original algorithm's reward on $H_B$; and the offline optimum of $H_B$ is within a $1-O(\\sqrt{\\log(cd)/c})$ factor of the offline optimum of the original instance, mediated by an expected LP relaxation. Together these comparisons let an old fixed-inventory algorithm inherit its guarantee in a new setting.","pith_inferences":["Outside the paper's framework, the thresholding principle suggests that any online algorithm with a monotone competitive ratio in a large-capacity regime can absorb small frequent exogenous inflows by delaying their conversion into usable capacity; the delay cost is $o(1)$ whenever the threshold is $o(c_{\\min})$, so similar tricks may apply to online packing, queueing, and capacity-scaling decisio","The two-point distribution of stochastic replenishment is used in one concentration argument, so a natural test is whether independent continuous or sub-Gaussian replenishments with the same means and tail bound $M$ satisfy the same probability bound, or whether the fluid discount $\\epsilon$ must be enlarged for heavier-tailed inflows.","The paper leaves open a myopic policy that uses small replenishments immediately; a concrete experiment would run $\\mathrm{ALG}$ without batching but with a reserved safety buffer of size roughly $\\epsilon c_{\\min}$ and compare its competitive ratio with the batched extension's rate, which would show whether the batching delay is avoidable at the cost of a small inventory reserve."],"forward_implications":["Every existing competitive-ratio result for adversarial online allocation without replenishment that fits the framework becomes, at essentially no asymptotic cost, a result for the same problem with arbitrary adversarial replenishment in the large-inventory regime.","In the stochastic-arrival case, existing near-optimal algorithms for problems such as online matching and assortment optimization extend losslessly provided each replenishment is bounded by $M=o(c_{\\min})$, so the extension covers settings where the original guarantee was already near $1$.","The impossibility theorem identifies the boundary: when a single replenishment can be as large as the starting inventory, or when arrivals are stochastic and replenishment is adversarial, no online algorithm can preserve near-optimal performance in general.","The two-step analysis (algorithm versus batched benchmark, then batched benchmark versus LP) gives a template for proving similar extensions: only the first step depends on the specific algorithm, while the second depends only on the resource-allocation framework."],"supporting_citations":[{"why":"Supplies the observation that a sufficiently large replenishment can be treated as a new resource type and defines the large-budget regime whose guarantees the black-box extension inherits.","marker":"[2]"},{"why":"Introduced the batching idea and the first extension of the Inventory Balancing algorithm to arbitrary adversarial replenishment, which this paper generalizes into a black-box method.","marker":"[11]"},{"why":"Provides the general framework, the expected LP relaxation, and the near-optimal stochastic algorithms whose guarantees are extended by the batching construction.","marker":"[16]"},{"why":"Prior baseline showing that a simple greedy policy is $1/2$-competitive with arbitrary replenishment; the paper situates its stronger lossless extension against this guarantee.","marker":"[10]"},{"why":"Supplies the Chernoff-type concentration bound (Lemma A.1) used to control fallback probabilities and the LP-to-OPT gap.","marker":"[12]"}],"fun_headline_variants":["Black-box batching tames replenished inventory","Batching refills to preserve allocation ratios","Online allocation survives unknown refills","Exogenous refills handled by black-box batching","Batching refills keep allocation ratios intact"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The stochastic-replenishment guarantee rests on the assumption that every replenishment of every resource is an independent two-point random variable (either nothing or one fixed amount), all bounded by a quantity $M$ that is asymptotically smaller than the smallest starting inventory; if replenishment is continuous, correlated, or sometimes as large as the inventory, the lossless guarantee is no longer claimed.","fun_headline_variants_meta":{"raw":{"variants":["Black-box batching tames replenished inventory","Batching refills to preserve allocation ratios","Online allocation survives unknown refills","Exogenous refills handled by black-box batching","Batching refills keep allocation ratios intact"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000838,"raw_usage":{"total_tokens":3629,"prompt_tokens":893,"completion_tokens":2736,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":509,"completion_tokens_details":{"reasoning_tokens":2669}},"tokens_in":509,"tokens_out":2736,"duration_ms":509526,"temperature":1.0,"reasoning_tokens":2669,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T15:47:46.030837+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run $\\mathrm{ALG\\text{-}B}$ on a family of stochastic instances with $M=o(c)$ where each replenishment is an independent two-point variable, and compare its average reward with the offline value on the same realizations; if the ratio falls below $\\alpha(O(M^{1/3}c^{2/3}\\log(cd)))(1-O(M^{1/3}c^{-1/3}\\log(cd)))$ by a non-vanishing amount, the stochastic theorem's constants are wrong. For the adversarial theorem, an instance in which replenishment arrives one unit per period while the threshold is $\\sqrt{c}$ would expose whether the delay loss is actually bounded by the claimed $O(\\sqrt{\\log(cd)/c})$ factor. The explicit $G_S$ instance in Section 4.3 is a built-in falsifier for any claim that the lossless regime extends to $M=\\Omega(c)$: any online algorithm there has expected reward at most $(1+\\gamma)c$ against an offline value of $(1+3\\gamma/2)c$.","supporting_citations":[{"cited_title":"Journal of the ACM (JACM) 54(5), 22 (2007)","cited_arxiv_id":null,"evidence_quote":"Supplies the observation that a sufficiently large replenishment can be treated as a new resource type and defines the large-budget regime whose guarantees the black-box extension inherits."},{"cited_title":"Available at SSRN 3795056 (2021)","cited_arxiv_id":null,"evidence_quote":"Introduced the batching idea and the first extension of the Inventory Balancing algorithm to arbitrary adversarial replenishment, which this paper generalizes into a black-box method."},{"cited_title":"Journal of the ACM (JACM) 66(1), 1–41 (2019)","cited_arxiv_id":null,"evidence_quote":"Provides the general framework, the expected LP relaxation, and the near-optimal stochastic algorithms whose guarantees are extended by the batching construction."},{"cited_title":"Mathematics of Operations Research 34(2), 333–350 (2009)","cited_arxiv_id":null,"evidence_quote":"Prior baseline showing that a simple greedy policy is $1/2$-competitive with arbitrary replenishment; the paper situates its stronger lossless extension against this guarantee."},{"cited_title":"Operations Research (2025)","cited_arxiv_id":null,"evidence_quote":"Supplies the Chernoff-type concentration bound (Lemma A.1) used to control fallback probabilities and the LP-to-OPT gap."}],"review_version":1}