A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation

Rajan Udwani; Suho Kang; Ziyang Liu

REVIEW 3 major objections 5 minor 27 references

A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Batching lets online allocation algorithms keep their competitive-ratio guarantees when inventory is exogenously replenished, so long as the starting inventory is large.

desk verdict 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. read the letter →

arxiv 2507.14812 v1 pith:IRUBFLPS submitted 2025-07-20 cs.DS

Suho Kang , Ziyang Liu , Rajan Udwani This is my paper · ORCID

classification cs.DS MSC 68W2768W4090C27

keywords onlineresourceallocationexogenousreplenishmentcompetitiveratioblack-boxtransformationbatchingextensionadversarialarrivalsstochasticlargeinventoryregime

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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$.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

What'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.

What'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.

Section 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).

Who 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.

Recommendation: 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.

Referee Report

3 major / 5 minor

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.

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 (3)

[Appendix A.2, Lemma 4.2 (used in §4.2)] 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 4.2, comparison of LP(HB) and LP(H)] 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 4.2, first inequality for ALG-B_j(H)] 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.

minor comments (5)

[Abstract and Section 2] 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.
[Algorithm 2 and Section 4.2] 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 4.1] 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.
[Appendix A.2, Lemma 4.2] 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 4.3, proof of Theorem 2.3] 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γ).

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: ALG-B's guarantee is reduced to ALG's assumed competitive ratio through explicit LP benchmarks, not by construction.

full rationale

The paper's derivation is a self-contained theoretical reduction. ALG-B is defined to simulate ALG on a batched, replenishment-free instance H_B, and the proof separately bounds ALG-B(H) vs ALG(H_B), ALG(H_B)/OPT(H_B) by the assumed input ratio alpha(c_B), and OPT(H_B)/OPT(H) through LP relaxations (Lemmas 4.1 and 4.2). The competitive ratio alpha(c) is an input assumption, not derived from the conclusion; the thresholds c_B = sqrt(c_min) (adversarial) and epsilon = ((3M/c_min) log(c_min d))^{1/3} (stochastic) are analytic design choices, not fitted parameters. The only self-citations are the IPCO early-version pointer [1], which is not load-bearing, and Lemma A.1, a standard Chernoff bound credited to [12] (co-authored by one of the present authors); this is a general parameter-free concentration result with independent content, so it does not raise the circularity score. Separately, I note a correctness risk in the stochastic proof: in Appendix A.2, the rounding proof of Lemma 4.2 asserts E[sum A bar-X] <= (c_i + sum zeta_i(t))/(1+delta), using realized replenishment in the Chernoff mean, whereas LP feasibility (constraint (3)) gives only expected replenishment sum q_it; on low-replenishment paths this inequality is unsupported, and Section 4.2 also states only LP(H_B) <= (1-epsilon)LP(H) where the final factor would require a lower bound. This is a proof gap, not a circular reduction by construction, so under the hard rules it is weighed as a correctness risk and does not increase the circularity score.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard LP-relaxation and concentration tools plus the paper's batching construction. There are no fitted free parameters in the usual sense; the threshold and epsilon are analytic design choices. The main modeling restrictions are the two-point stochastic replenishment assumption and the large-inventory regime.

free parameters (3)

Batching threshold cB (adversarial case) = sqrt(cmin)
Chosen to balance the tradeoff between keeping the batched instance in the large-inventory regime and limiting reward loss from delayed use of replenished inventory; not fitted to data.
Epsilon and batching threshold cB = epsilon * cmin (stochastic case) = min((3M/cmin * log(cd))^(1/3), 1)
Chosen so that the probability of a capacity violation is at most 1/(cd) via Chernoff; a design parameter, not fitted to data.
Delta in Lemma 4.2 = sqrt(3 log(cd)/c)
Chosen in the randomized rounding proof to make the failure probability O(1/(cd)); a standard concentration parameter.

assumptions (5)

domain assumption H0 is closed under adding or removing a resource type
Required so that the batched instance HB belongs to the same family H0 that ALG was designed for (Section 2.2).
domain assumption Each stochastic replenishment is an independent two-point random variable supported on {0, w_ij} with w_ij <= M
Used for the Chernoff concentration argument in Section 4.2; excludes continuous or correlated replenishment despite the abstract's 'arbitrary' wording.
domain assumption Large-inventory regime: cmin is large and, in the stochastic case, M = o(cmin)
All guarantees are asymptotic, with 1 - O(...) factors vanishing as c grows; Theorem 2.3 shows the regime is necessary.
domain assumption Without loss of generality, ALG never implements a non-trivial action with zero reward for every resource type
Stated in Section 2.2; used to argue that unavailable batched actions (with reward set to 0) are never chosen, keeping ALG-B consistent with ALG on the batched instance.
standard math LP(H) is a valid upper bound on OPT(H) and the gap is O(sqrt(log(cd)/cmin))
Lemmas 4.1 and 4.2 provide proofs, but the proof of Lemma 4.2 has a gap in the stochastic case (see red flags).

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation." pith.science (2026). https://pith.science/paper/IRUBFLPS

@misc{pith2026250714812,
  author       = {Pith},
  title        = {Pith review of: A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IRUBFLPS}},
  note         = {Machine review of arXiv:2507.14812}
}

read the original abstract

In a typical online resource allocation problem, we start with a fixed inventory of resources and make online allocation decisions in response to resource requests that arrive sequentially over a finite horizon. We consider settings where the inventory is replenished over time according to an unknown exogenous process. We introduce black-box methods that extend any existing algorithm, originally designed without considering replenishment, into one that works with an arbitrary (adversarial or stochastic) replenishment process. Our approach preserves the original algorithm's competitive ratio in regimes with large initial inventory, thereby enabling the seamless integration of exogenous replenishment into a large body of existing algorithmic results for both adversarial and stochastic arrival models.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 26 canonical work pages

[1]

In: International Conference on Integer Programming and Combinatorial Optimization, pp

Kang, S., Liu, Z., Udwani, R.: A black-box approach for exogenous replen- ishment in online resource allocation. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 326–340 (2025). Springer

work page 2025
[2]

Journal of the ACM (JACM) 54(5), 22 (2007)

Mehta, A., Saberi, A., Vazirani, U., Vazirani, V.: Adwords and generalized online matching. Journal of the ACM (JACM) 54(5), 22 (2007)

work page 2007
[3]

Management science 44(11-part-1), 1577–1593 (1998)

Talluri, K., Van Ryzin, G.: An analysis of bid-price controls for network revenue management. Management science 44(11-part-1), 1577–1593 (1998)

work page 1998
[4]

Management Science 60(6), 1532–1551 (2014)

Golrezaei, N., Nazerzadeh, H., Rusmevichientong, P.: Real-time optimization of personalized assortments. Management Science 60(6), 1532–1551 (2014)

work page 2014
[5]

Management Science 66(7), 2820–2844 (2020)

Rusmevichientong, P., Sumida, M., Topaloglu, H.: Dynamic assortment optimiza- tion for reusable products with random usage durations. Management Science 66(7), 2820–2844 (2020)

work page 2020
[6]

Foundations and Trends ® in Theoretical Computer Science 8(4), 265–368 (2013)

Mehta, A.: Online matching and ad allocation. Foundations and Trends ® in Theoretical Computer Science 8(4), 265–368 (2013)

work page 2013
[7]

Online Matching: A Brief Survey

Huang, Z., Tang, Z.G., Wajc, D.: Online matching: A brief survey. arXiv preprint arXiv:2407.05381 (2024)

work page Pith review arXiv 2024
[8]

In: 43rd IARCS Annual Conference on Foundations 25 of Software Technology and Theoretical Computer Science (FSTTCS 2023), pp

Vazirani, V.V.: Towards a practical, budget-oblivious algorithm for the adwords problem under small bids. In: 43rd IARCS Annual Conference on Foundations 25 of Software Technology and Theoretical Computer Science (FSTTCS 2023), pp. 21–1 (2023). Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik

work page 2023

Show all 27 references

[9]

Management Science 71(2), 1009–1026 (2025)

Udwani, R.: Adwords with unknown budgets and beyond. Management Science 71(2), 1009–1026 (2025)

2025
[10]

Mathematics of Operations Research 34(2), 333–350 (2009)

Chan, C.W., Farias, V.F.: Stochastic depletion problems: Effective myopic poli- cies for a class of dynamic optimization problems. Mathematics of Operations Research 34(2), 333–350 (2009)

2009
[11]

Available at SSRN 3795056 (2021)

Feng, Y., Niazadeh, R., Saberi, A.: Robustness of online inventory balancing algorithm to inventory shocks. Available at SSRN 3795056 (2021)

2021
[12]

Operations Research (2025)

Goyal, V., Iyengar, G., Udwani, R.: Asymptotically optimal competitive ratio for online allocation of reusable resources. Operations Research (2025)

2025
[13]

Available at SSRN (2024)

Ekbatani, F., Feng, Y., Kash, I., Niazadeh, R.: Online job assignment. Available at SSRN (2024)

2024
[14]

arXiv preprint arXiv:2402.08775 (2024)

Tr¨ obst, T., Udwani, R.: Almost tight bounds for online hypergraph matching. arXiv preprint arXiv:2402.08775 (2024)

2024 arXiv
[15]

Alaei, S., Hajiaghayi, M., Liaghat, V.: Online prophet-inequality matching with applications to ad allocation, 18–35 (2012)

2012
[16]

Journal of the ACM (JACM) 66(1), 1–41 (2019)

Devanur, N.R., Jain, K., Sivan, B., Wilkens, C.A.: Near optimal online algorithms and fast approximation algorithms for resource allocation problems. Journal of the ACM (JACM) 66(1), 1–41 (2019)

2019
[17]

In: Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing, pp

Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on- line bipartite matching. In: Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing, pp. 352–358 (1990)

1990
[18]

Operations Research 71(2), 563–580 (2023)

Goyal, V., Udwani, R.: Online matching with stochastic rewards: Optimal com- petitive ratio via path-based formulation. Operations Research 71(2), 563–580 (2023)

2023
[19]

Theoretical Computer Science 233(1-2), 319–325 (2000)

Kalyanasundaram, B., Pruhs, K.R.: An optimal deterministic algorithm for online b-matching. Theoretical Computer Science 233(1-2), 319–325 (2000)

2000
[20]

In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pp

Mehta, A., Panigrahi, D.: Online matching with stochastic rewards. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pp. 728–737 (2012). IEEE

2012
[21]

In: Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp

Mehta, A., Waggoner, B., Zadimoghaddam, M.: Online stochastic matching with unequal probabilities. In: Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1388–1404 (2014). SIAM 26

2014
[22]

Management Science 68(7), 4772–4785 (2022)

Gong, X.-Y., Goyal, V., Iyengar, G.N., Simchi-Levi, D., Udwani, R., Wang, S.: Online assortment optimization with reusable resources. Management Science 68(7), 4772–4785 (2022)

2022
[23]

Operations Research 72(5), 1861–1873 (2024)

Feng, Y., Niazadeh, R., Saberi, A.: Near-optimal bayesian online assortment of reusable resources. Operations Research 72(5), 1861–1873 (2024)

2024
[24]

Mathematics of Operations Research 34(2), 270–286 (2009)

Buchbinder, N., Naor, J.: Online primal-dual algorithms for covering and packing. Mathematics of Operations Research 34(2), 270–286 (2009)

2009
[25]

Operations Research 68(3), 834–855 (2020)

Ma, Y., Rusmevichientong, P., Sumida, M., Topaloglu, H.: An approxima- tion algorithm for network revenue management under nonstationary arrivals. Operations Research 68(3), 834–855 (2020)

2020
[26]

arXiv preprint arXiv:2305.05829 (2023)

Jiang, J.: Constant approximation for network revenue management with markovian-correlated customer arrivals. arXiv preprint arXiv:2305.05829 (2023)

2023 arXiv
[27]

Ma, W., MacRury, C., Zhang, J.: Online contention resolution schemes for network revenue management and combinatorial auctions. arXiv preprint arXiv:2403.05378 (2024) 27 A Appendix A.1 Illustrative Example of Batching Extension Example 1 (Under Adversarial Arrival and Replenis...

2024 arXiv

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

In: International Conference on Integer Programming and Combinatorial Optimization, pp

Kang, S., Liu, Z., Udwani, R.: A black-box approach for exogenous replen- ishment in online resource allocation. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 326–340 (2025). Springer

work page 2025

[2] [2]

Journal of the ACM (JACM) 54(5), 22 (2007)

Mehta, A., Saberi, A., Vazirani, U., Vazirani, V.: Adwords and generalized online matching. Journal of the ACM (JACM) 54(5), 22 (2007)

work page 2007

[3] [3]

Management science 44(11-part-1), 1577–1593 (1998)

Talluri, K., Van Ryzin, G.: An analysis of bid-price controls for network revenue management. Management science 44(11-part-1), 1577–1593 (1998)

work page 1998

[4] [4]

Management Science 60(6), 1532–1551 (2014)

Golrezaei, N., Nazerzadeh, H., Rusmevichientong, P.: Real-time optimization of personalized assortments. Management Science 60(6), 1532–1551 (2014)

work page 2014

[5] [5]

Management Science 66(7), 2820–2844 (2020)

Rusmevichientong, P., Sumida, M., Topaloglu, H.: Dynamic assortment optimiza- tion for reusable products with random usage durations. Management Science 66(7), 2820–2844 (2020)

work page 2020

[6] [6]

Foundations and Trends ® in Theoretical Computer Science 8(4), 265–368 (2013)

Mehta, A.: Online matching and ad allocation. Foundations and Trends ® in Theoretical Computer Science 8(4), 265–368 (2013)

work page 2013

[7] [7]

Online Matching: A Brief Survey

Huang, Z., Tang, Z.G., Wajc, D.: Online matching: A brief survey. arXiv preprint arXiv:2407.05381 (2024)

work page Pith review arXiv 2024

[8] [8]

In: 43rd IARCS Annual Conference on Foundations 25 of Software Technology and Theoretical Computer Science (FSTTCS 2023), pp

Vazirani, V.V.: Towards a practical, budget-oblivious algorithm for the adwords problem under small bids. In: 43rd IARCS Annual Conference on Foundations 25 of Software Technology and Theoretical Computer Science (FSTTCS 2023), pp. 21–1 (2023). Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik

work page 2023