Pith. sign in

REVIEW 1 major objections 3 minor 3 cited by

Improved Approximations for Stationary Bipartite Matching: Beyond Probabilistic Independence

T0 review · 1 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read For stationary online bipartite matching, the paper breaks the 1 - 1/e approximation barrier and improves the known competitive ratio to 1 - 1/sqrt(e) + η.

desk verdict Serious attempt at breaking 1-1/e in stationary bipartite matching, but a likely invalid Paley-Zygmund step in Lemma 3.20 leaves the universal constant unsupported. read the letter →

arxiv 2411.08218 v1 pith:XCDEUEBO submitted 2024-11-12 cs.DS

Alireza AmaniHamedani , Ali Aouad , Tristan Pollner , Amin Saberi This is my paper · ORCID
classification cs.DS
keywords onlinenodesalgorithmofflinematchingapproximationsbipartitecompetitive
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

Consider a system with two kinds of agents. Some agents, such as patients on a transplant list, arrive over time and can wait only a random amount of time before leaving. Other agents, such as donated organs, arrive at random times and must be assigned immediately. Each possible match gives a reward. The question is how to assign arrivals online to maximize long-run reward. The best guarantee known until now was 1 - 1/e of the reward of the best possible online policy.

The paper combines a linear program that gives an upper bound on the best policy, a correlated randomization technique called pivotal sampling, and a greedy backup algorithm. In easy instances the LP-based algorithm already beats 1 - 1/e. The remaining hard instances have a very special structure: rewards are almost vertex-weighted and each online type almost always has an available neighbor. For those instances the paper runs Balanced Greedy, which randomly splits each offline type into a top and a bottom copy and always prefers top copies. The analysis tracks a simplified Markov chain in which top queues are independent and bottom queues are emptied only when the top queues are empty. Using renewal theory, the paper shows that under this simplified chain an arriving online node sees no available neighbor with probability strictly below 1/e, which gives the constant improvement.

The proof is long but self-contained. The main risk is in the technical lemmas that control correlation between bottom queues; the paper states a small CDF inequality in the wrong direction in one spot, though the surrounding quantile argument uses the correct direction.

Extended reading notes

Core claim

Theorem 1.1: there exists a polynomial-time algorithm whose expected average reward is at least (1 - 1/e + δ) times the optimal online policy's reward for a universal constant δ > 0. If the paper is correct, this breaks the 1 - 1/e barrier in stationary bipartite matching. The same proof also yields a (1 - 1/sqrt(e) + η)-competitive algorithm against the offline optimum (Theorem 4.1).

Load-bearing premise

Lemma 3.20, the core-set concentration lemma, is load-bearing: its proof assumes that the neighborhood of any hard online type j contains a subset I_core ⊆ N_j^↑ satisfying inequalities (20) and (21), so that the ratio Λ̃/Γ̃ is at least 0.045 (Appendix D.7.1). This ratio is what makes the renewal-theory concentration bounds (23) and (24) effective, and it ultimately supplies the constant boost exp(-0.1 c̃) in the proof of Lemma 3.11. If the counting argument fails at the ε' = b^{-1}(2ε) used in Definition 3.4, the VWHC analysis does not produce a universal ζ.

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.

Referee Report

1 major / 3 minor

Summary. This paper studies stationary online bipartite matching in which offline nodes arrive according to Poisson processes and have exponentially distributed patience, while online nodes must be matched immediately. The main claim is Theorem 1.1: a polynomial-time algorithm whose expected long-run average reward is at least (1−1/e+δ) times the optimal online policy's reward for a universal δ>0, thereby breaking the 1−1/e barrier established by Aouad and Saritaç. The proof introduces a tightened LP relaxation (TLPon) with subset constraints, proves a (1−1/e)-approximation via independent Markov chains and pivotal sampling, identifies three 'easy' cases in which the analysis is loose, and then analyzes a Balanced Greedy algorithm on the remaining vertex-weighted highly-connected instances using weakly correlated Markov chains and renewal-theoretic concentration. A byproduct is a (1−1/√e+η)-competitive algorithm against the offline optimum (Theorem 4.1).

Significance. If the main theorem is correct, it is a significant advance: it answers an open direction in stationary matching by showing that correlation in the offline queueing process can be exploited algorithmically, and it improves the best-known competitive ratio. The paper's strengths include a clean stochastic-dominance coupling for the baseline, a non-trivial use of pivotal sampling for dependent rounding, and a clear reduction of the hard case to a structured VWHC instance. No code or machine-checked proofs are included; the contribution is analytic and the constants are non-explicit but in principle computable. The main findings are falsifiable: the claimed universal constant either follows from the supplied lemmas or not. The load-bearing gap identified below prevents me from recommending acceptance in the current form.

major comments (1)
  1. [§3.4, Appendix D.7.2, inequalities (23) and (49)–(52)] The concentration step in Lemma 3.20 is not justified as written. Fact D.3 is invoked with θ=1/2, but the event whose probability is needed is {Σ_{t=1}^T η^n_t ≥ 1/(4δ′Γ̃)}. From T=⌈Λ̃/(δ′Γ̃)⌉ and E[η^n_t] ≥ (1−ǫ′)u(ǫ′,κ)/Λ̃ (inequality (48)), one has E[Ση^n_t] ≥ (1−ǫ′)u(ǫ′,κ)/(δ′Γ̃). Hence threshold/E[Ση^n_t] = 1/[4(1−ǫ′)u(ǫ′,κ)], which is ≈1.93 for ǫ′=κ=0.1 and can exceed 1 for admissible parameters; when the threshold is above the mean, Paley–Zygmund with any θ<1 gives no lower bound on the desired tail. Even when the ratio is below 1, the correct factor is (1−ratio)^2 rather than the 1/4 used in (50)–(52), so the constants c0, δ̄, and ultimately ζ in Lemma 3.11 are not established. The authors should supply a valid concentration bound for the renewal sum (for instance by enlarging T so that the target threshold is at most a constant fraction of the mean, or by an exponential tail bound for the hyperexponential variables) and re-derive the constants.
minor comments (3)
  1. [Proof of Lemma 3.11, after equation (16)] The inequality F_i(u,τ_i) ≤ F̃_i(u,τ_i) has the wrong direction; Lemma 3.14's stochastic dominance gives F_i ≥ F̃_i, and the subsequent integral upper bound is valid only with that corrected direction.
  2. [Proof of Lemma 3.13] The symbol sMc appears without definition in the phrase 'the depletion of sMc'; this should be a named process or defined notation.
  3. [Main theorems] The universal constants ζ, δ, and η are asserted to exist but never quantified; this is acceptable for an existence proof, but the paper would be more useful if the main theorem stated how the constants are obtained from c0, δ̄, and f(·).
Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

No free parameters are fitted to data. The constants δ, ζ, c, and c̃ are existential universal constants obtained from inequalities, not tuned to instances. The axioms are standard probabilistic tools plus the model assumptions. The only ad hoc construct is the analysis-only binary queue truncation, which is clearly labeled in the paper.

assumptions (7)
  • standard math PASTA property for Poisson arrivals (Lemma A.7)
    Used to convert long-run average reward into an expectation under the stationary distribution of the queue process. This is a standard result from Wolff (1982).
  • standard math Stochastic dominance criteria for continuous-time Markov chains (Lemma C.3)
    Used to compare the true queue process with independent Markov chains and with weakly correlated Markov chains. The criterion is standard for coupled CTMCs.
  • standard math Convex order facts, including Fact 2.11 and the thinning coupling p*Pois(λ) ≤cv Pois(pλ)
    Used to bound expectations of min(1,R_j(w)) by replacing scaled Poisson variables with Poisson variables of the same mean and larger variability.
  • standard math Hardy-Littlewood rearrangement inequality (Fact 3.15)
    Used to upper bound the expectation of a product of dependent random variables by the integral of the product of quantile functions.
  • domain assumption Poisson process model with exponential patience
    The entire model is defined by Poisson arrival rates and exponential offline patience. The result is proved only for this model.
  • domain assumption Existence and value of the optimal online policy via Bellman equations
    OPT_on is defined as the solution of a dynamic program. The paper relies on standard MDP theory for the existence of such a policy.
  • ad hoc to paper Analysis-only binary queue truncation with loss factor 1 - ε^2/n
    Property (v) and Appendix D.3.1 assume queue lengths above 1 can be ignored after sufficiently many type splits. This is a proof device, not part of the implemented algorithm.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved Approximations for Stationary Bipartite Matching: Beyond Probabilistic Independence." pith.science (2026). https://pith.science/paper/XCDEUEBO

@misc{pith2026241108218,
  author       = {Pith},
  title        = {Pith review of: Improved Approximations for Stationary Bipartite Matching: Beyond Probabilistic Independence},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XCDEUEBO}},
  note         = {Machine review of arXiv:2411.08218}
}
abstract

We study stationary online bipartite matching, where both types of nodes--offline and online--arrive according to Poisson processes. Offline nodes wait to be matched for some random time, determined by an exponential distribution, while online nodes need to be matched immediately. This model captures scenarios such as deceased organ donation and time-sensitive task assignments, where there is an inflow of patients and workers (offline nodes) with limited patience, while organs and tasks (online nodes) must be assigned upon arrival. We present an efficient online algorithm that achieves a $(1-1/e+\delta)$-approximation to the optimal online policy's reward for a constant $\delta > 0$, simplifying and improving previous work by Aouad and Sarita\c{c} (2022). Our solution combines recent online matching techniques, particularly pivotal sampling, which enables correlated rounding of tighter linear programming approximations, and a greedy-like algorithm. A key technical component is the analysis of a stochastic process that exploits subtle correlations between offline nodes, using renewal theory. A byproduct of our result is an improvement to the best-known competitive ratio--that compares an algorithm's performance to the optimal offline policy--via a $(1-1/\sqrt{e} + \eta)$-competitive algorithm for a universal constant $\eta > 0$, advancing the results of Patel and Wajc (2024).

Figures

Figures reproduced from arXiv: 2411.08218 by the authors.

Figure 1
Figure 1. Schematic visualization of “Instance Transformation” In the original instance, red nodes are hard online types and green node is easy. Dashed edges have either a reward not in [rj ,(1 + ǫ)rj ] or a proposal probability pi,j < 1 − ǫ ′ . In the second step, each offline node (on the left) is splitted into two identical nodes. Algorithm 2 Balanced Greedy 1: Solve (TLPon) for {xi,j} 2: Invoke the Instance Transformation… view at source ↗
Figure 2
Figure 2. Schematic visualization of J correl and J indep Lemma 3.20. There exist constants c0, ¯δ ∈ (0, 1) independent of ǫ, κ such that if δ ≤ ¯δ, for each i ∈ N ↓ j , we have Pr   X k∈Jcorrel∩Ni γkθi,k ≤ (1 − c0) · ti X k∈Jcorrel∩Ni γk [PITH_FULL_IMAGE:figures/full_fig_p022_2.png] view at source ↗
Figure 3
Figure 3. Family of instances where Algorithm 1 is (1 − 1/e + o(1))-approximate C Deferred Proofs of Section 2 C.1 Proof of Claim 2.1 Claim 2.1. Let OPT(TLPon) be the optimal value of (TLPon). Then, OPT(TLPon) ≥ OPTon. Proof. For the first inequality, for every t ≥ 0 let OPTi,j [0, t] denote the number of matches between types i and j made by the optimum online algorithm in the time range [0, t]. Similarly let OPTi,a[0, t] de… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Adaptive Approximation Schemes for Matching Queues

    cs.DS 2025-01 conditional novelty 8.0 of 10

    Adaptive queue-length-based matching policies can be approximated to within (1 minus epsilon) in polynomial time for constant-size networks and for fixed-dimensional Euclidean networks with abandonment.

  2. Greedy Dynamic Matching

    cs.DS 2025-07 conditional novelty 7.0 of 10

    A linear-program-guided greedy policy provably achieves the optimal competitive ratio 1/2 against an omniscient benchmark in dynamic matching with homogeneous abandonment rates.

  3. Constant-Factor Algorithms for Revenue Management with Consecutive Stays

    econ.TH 2025-06 accept novelty 7.0 of 10

    A new algorithmic framework guarantees a fixed fraction (between 15% and 63%) of optimal online revenue for consecutive-stay seat and room allocation, with or without customer choice.

Reference graph

Works this paper leans on

64 extracted references · 60 canonical work pages · cited by 3 Pith papers

  1. [1]

    Adaptive policies and approximation schemes for dynamic matching

    Alireza AmaniHamedani, Ali Aouad, and Amin Saberi. Adaptive policies and approximation schemes for dynamic matching. Working paper , 2024

    work page 2024

  2. [2]

    Edge-weighted online windowed matching

    Itai Ashlagi, Maximilien Burq, Chinmoy Dutta, Patrick Jaillet, Amin Saberi, and Chris Sholley. Edge-weighted online windowed matching. Math. Oper. Res. , 48(2):999--1016, 2023

    work page 2023

  3. [3]

    Secretary and online matching problems with machine learned advice

    Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. Discret. Optim. , 48(Part 2):100778, 2023

    work page 2023

  4. [4]

    Online vertex-weighted bipartite matching and single-bid budgeted allocations

    Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1253--1264, 2011

    work page 2011

  5. [5]

    A nonparametric framework for online stochastic matching with correlated arrivals

    Ali Aouad and Will Ma. A nonparametric framework for online stochastic matching with correlated arrivals. In Kevin Leyton - Brown, Jason D. Hartline, and Larry Samuelson, editors, Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023 , page 114. ACM , 2023

    2023

  6. [6]

    Kidney exchange: An operations perspective

    Itai Ashlagi and Alvin E Roth. Kidney exchange: An operations perspective. Management Science , 67(9):5455--5478, 2021

    work page 2021

  7. [7]

    Dynamic stochastic matching under limited time

    Ali Aouad and \"O mer Sar ta c . Dynamic stochastic matching under limited time. Operations Research , 70(4):2349--2383, 2022

    work page 2022

  8. [8]

    Multiway online correlated selection

    Guy Blanc and Moses Charikar. Multiway online correlated selection. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 1277--1284. IEEE, 2022

    work page 2021

Show all 64 references
  1. [9]

    Max-weight online stochastic matching: Improved approximations against the online benchmark

    Mark Braverman, Mahsa Derakhshan, and Antonio Molina Lovett. Max-weight online stochastic matching: Improved approximations against the online benchmark. In Proceedings of the 23rd ACM Conference on Economics and Computation , pages 967--985, 2022

    2022

  2. [10]

    New philosopher inequalities for online bayesian matching, via pivotal sampling

    Mark Braverman, Mahsa Derakhshan, Tristan Pollner, Amin Saberi, and David Wajc. New philosopher inequalities for online bayesian matching, via pivotal sampling. arXiv preprint arXiv:2407.15285 , 2024

    2024 arXiv

  3. [11]

    Dynamic programming and optimal control: Volume I , volume 4

    Dimitri Bertsekas. Dynamic programming and optimal control: Volume I , volume 4. Athena scientific, 2012

    2012

  4. [12]

    Stability of the bipartite matching model

    Ana Bu s i \'c , Varun Gupta, and Jean Mairesse. Stability of the bipartite matching model. Advances in Applied Probability , 45(2):351--378, 2013

    2013

  5. [13]

    Rearrangement inequalities for functionals with monotone integrands

    Almut Burchard and Hichem Hajaiej. Rearrangement inequalities for functionals with monotone integrands. Journal of Functional Analysis , 233(2):561--582, 2006

    2006

  6. [14]

    On the pathwise comparison of jump processes driven by stochastic intensities

    Andreas Brandt and G \"u nter Last. On the pathwise comparison of jump processes driven by stochastic intensities. Mathematische Nachrichten , 167(1):21--42, 1994

    1994

  7. [15]

    Analysis of an optimal policy in dynamic bipartite matching models

    Arnaud Cadas, Josu Doncel, and Ana Bu s i \'c . Analysis of an optimal policy in dynamic bipartite matching models. Performance Evaluation , 154:102286, 2022

    2022

  8. [16]

    Multi-parameter mechanism design and sequential posted pricing

    Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC) , pages 311--320, 2010

    2010

  9. [17]

    Stochastic online correlated selection

    Ziyun Chen, Zhiyi Huang, and Enze Sun. Stochastic online correlated selection. arXiv preprint arXiv:2408.12524 , 2024

    2024 arXiv

  10. [18]

    Dynamic weighted matching with heterogeneous arrival and departure rates

    Natalie Collina, Nicole Immorlica, Kevin Leyton-Brown, Brendan Lucier, and Neil Newman. Dynamic weighted matching with heterogeneous arrival and departure rates. In Web and Internet Economics: 16th International Conference, WINE 2020, Beijing, China, December 7--11, 2020, Proc...

    2020

  11. [19]

    Dynamic matching via weighted myopia with application to kidney exchange

    John Dickerson, Ariel Procaccia, and Tuomas Sandholm. Dynamic matching via weighted myopia with application to kidney exchange. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 26, pages 1340--1346, 2012

    2012

  12. [20]

    Dickerson, Karthik A

    John P. Dickerson, Karthik A. Sankararaman, Aravind Srinivasan, and Pan Xu. Allocation problems in ride-sharing platforms: Online matching with offline reusable resources. ACM Trans. Econ. Comput. , 9(3), June 2021

    2021

  13. [21]

    Prophet matching with general arrivals

    Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang. Prophet matching with general arrivals. Mathematics of Operations Research , 47(2):878--898, 2022

    2022

  14. [22]

    Echenique, N

    F. Echenique, N. Immorlica, V.V. Vazirani, and A.E. Roth. Online and Matching-Based Market Design . Cambridge University Press, 2023

    2023

  15. [23]

    A stronger impossibility for fully online matching

    Alexander Eckl, Anja Kirschbaum, Marilena Leichter, and Kevin Schewior. A stronger impossibility for fully online matching. Operations Research Letters , 49(5):802--808, 2021

    2021

  16. [24]

    Combinatorial auctions via posted prices

    Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 123--135, 2015

    2015

  17. [25]

    Edge-weighted online bipartite matching

    Matthew Fahrbach, Zhiyi Huang, Runzhou Tao, and Morteza Zadimoghaddam. Edge-weighted online bipartite matching. In Proceedings of the 61st Symposium on Foundations of Computer Science (FOCS) , pages 412--423, 2020

    2020

  18. [26]

    Online stochastic matching: Beating 1-1/e

    Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and S Muthukrishnan. Online stochastic matching: Beating 1-1/e. In Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS) , pages 117--126, 2009

    2009

  19. [27]

    Improved online correlated selection

    Ruiquan Gao, Zhongtian He, Zhiyi Huang, Zipei Nie, Bijun Yuan, and Yan Zhong. Improved online correlated selection. In Proceedings of the 62nd Symposium on Foundations of Computer Science (FOCS) , 2021. To Appear

    2021

  20. [28]

    Dependent rounding and its applications to approximation algorithms

    Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan. Dependent rounding and its applications to approximation algorithms. Journal of the ACM (JACM) , 53(3):324--360, 2006

    2006

  21. [29]

    Beating greedy for stochastic bipartite matching

    Buddhima Gamlath, Sagar Kale, and Ola Svensson. Beating greedy for stochastic bipartite matching. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 2841--2854. SIAM, 2019

    2019

  22. [30]

    Online matching with stochastic rewards: Optimal competitive ratio via path-based formulation

    Vineet Goyal and Rajan Udwani. Online matching with stochastic rewards: Optimal competitive ratio via path-based formulation. Operations Research , 71(2):563--580, 2023

    2023

  23. [31]

    Online matching with stochastic rewards: Advanced analyses using configuration linear programs

    Zhiyi Huang, Hanrui Jiang, Aocheng Shen, Junkai Song, Zhiang Wu, and Qiankun Zhang. Online matching with stochastic rewards: Advanced analyses using configuration linear programs. In Jugal Garg, Max Klimm, and Yuqing Kong, editors, Web and Internet Economics - 19th Internation...

    2023

  24. [32]

    How to match when all vertices arrive online

    Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu. How to match when all vertices arrive online. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC) , pages 17--29, 2018

    2018

  25. [33]

    Tight competitive ratios of classic matching algorithms in the fully online model

    Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang, Runzhou Tao, Xiaowei Wu, and Yuhao Zhang. Tight competitive ratios of classic matching algorithms in the fully online model. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2875--2886, 2019

    2019

  26. [34]

    Online stochastic matching, poisson arrivals, and the natural linear program

    Zhiyi Huang and Xinkai Shu. Online stochastic matching, poisson arrivals, and the natural linear program. In Samir Khuller and Virginia Vassilevska Williams, editors, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 682--693. ACM , 2021

    2021

  27. [35]

    The power of multiple choices in online stochastic matching

    Zhiyi Huang, Xinkai Shu, and Shuyi Yan. The power of multiple choices in online stochastic matching. In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022 , pages 91--103. ACM , 2022

    2022

  28. [36]

    Online matching: A brief survey

    Zhiyi Huang, Zhihao Gavin Tang, and David Wajc. Online matching: A brief survey. ACM SIGecom Exchanges , 22(1):135--158, 2024

    2024

  29. [37]

    Fully online matching ii: Beating ranking and water-filling

    Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Fully online matching ii: Beating ranking and water-filling. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 1380--1391. IEEE, 2020

    2020

  30. [38]

    Tail bounds for sums of geometric and exponential variables

    Svante Janson. Tail bounds for sums of geometric and exponential variables. Statistics & Probability Letters , 135:1--6, 2018

    2018

  31. [39]

    Online stochastic matching: New algorithms with better bounds

    Patrick Jaillet and Xin Lu. Online stochastic matching: New algorithms with better bounds. Mathematics of Operations Research , 2013

    2013

  32. [40]

    Online bipartite matching with advice: Tight robustness-consistency tradeoffs for the two-stage model

    Billy Jin and Will Ma. Online bipartite matching with advice: Tight robustness-consistency tradeoffs for the two-stage model. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Co...

    2022

  33. [41]

    Stochastic inequalities on partially ordered spaces

    Teturo Kamae, Ulrich Krengel, and George L O'Brien. Stochastic inequalities on partially ordered spaces. The Annals of Probability , 5(6):899--912, 1977

    1977

  34. [42]

    The stationary prophet inequality problem

    Kristen Kessel, Ali Shameli, Amin Saberi, and David Wajc. The stationary prophet inequality problem. In Proceedings of the 23rd ACM Conference on Economics and Computation , pages 243--244, 2022

    2022

  35. [43]

    An optimal algorithm for on-line bipartite matching

    Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC) , pages 352--358, 1990

    1990

  36. [44]

    Matroid prophet inequalities and applications to multi-dimensional mechanism design

    Robert Kleinberg and S Matthew Weinberg. Matroid prophet inequalities and applications to multi-dimensional mechanism design. Games and Economic Behavior , 113:97--115, 2019

    2019

  37. [45]

    Stochastic domination and markovian couplings

    F Javier L \'o pez, Servet Mart \' nez, and Gerardo Sanz. Stochastic domination and markovian couplings. Advances in Applied Probability , 32(4):1064--1076, 2000

    2000

  38. [46]

    Fully online matching with stochastic arrivals and departures

    Zihao Li, Hao Wang, and Zhenzhen Yan. Fully online matching with stochastic arrivals and departures. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 37, pages 12014--12021, 2023

    2023

  39. [47]

    A product form for the general stochastic matching model

    Pascal Moyal, Ana Bu s i \'c , and Jean Mairesse. A product form for the general stochastic matching model. Journal of Applied Probability , 58(2):449--468, 2021

    2021

  40. [48]

    Online stochastic matching: Online actions based on offline statistics

    Vahideh H Manshadi, Shayan Oveis Gharan, and Amin Saberi. Online stochastic matching: Online actions based on offline statistics. Mathematics of Operations Research , 37(4):559--573, 2012

    2012

  41. [49]

    Stability of the stochastic matching model

    Jean Mairesse and Pascal Moyal. Stability of the stochastic matching model. Journal of Applied Probability , 53(4):1064--1077, 2016

    2016

  42. [50]

    Online matching with stochastic rewards

    Aranyak Mehta and Debmalya Panigrahi. Online matching with stochastic rewards. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012 , pages 728--737. IEEE Computer Society, 2012

    2012

  43. [51]

    Adwords and generalized online matching

    Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. Journal of the ACM (JACM) , 54(5):22, 2007

    2007

  44. [52]

    Online dependent rounding schemes

    Joseph Naor, Aravind Srinivasan, and David Wajc. Online dependent rounding schemes. CoRR , abs/2301.08680, 2023

    2023 arXiv

  45. [53]

    Dynamic matching for real-time ride sharing

    Erhun \"O zkan and Amy R Ward. Dynamic matching for real-time ride sharing. Stochastic Systems , 10(1):29--70, 2020

    2020

  46. [54]

    Online stochastic max-weight bipartite matching: Beyond prophet inequalities

    Christos Papadimitriou, Tristan Pollner, Amin Saberi, and David Wajc. Online stochastic max-weight bipartite matching: Beyond prophet inequalities. Mathematics of Operations Research , 2023

    2023

  47. [55]

    Markov decision processes: discrete stochastic dynamic programming

    Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming . John Wiley & Sons, 2014

    2014

  48. [56]

    Combinatorial stationary prophet inequalities

    Neel Patel and David Wajc. Combinatorial stationary prophet inequalities. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 4605--4630. SIAM, 2024

    2024

  49. [57]

    Distributions on level-sets with applications to approximation algorithms

    Aravind Srinivasan. Distributions on level-sets with applications to approximation algorithms. In Proceedings of the 42nd Symposium on Foundations of Computer Science (FOCS) , pages 588--597, 2001

    2001

  50. [58]

    Stochastic orders

    Moshe Shaked and J George Shanthikumar. Stochastic orders . Springer, 2007

    2007

  51. [59]

    The greedy algorithm is not optimal for online edge coloring

    Amin Saberi and David Wajc. The greedy algorithm is not optimal for online edge coloring. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) , pages 109:1--109:18, 2021

    2021

  52. [60]

    (fractional) online stochastic matching via fine-grained offline statistics

    Zhihao Gavin Tang, Jinzhao Wu, and Hongxun Wu. (fractional) online stochastic matching via fine-grained offline statistics. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC) , pages 77--90, 2022

    2022

  53. [61]

    Improved bounds for fractional online matching problems

    Zhihao Gavin Tang and Yuhao Zhang. Improved bounds for fractional online matching problems. arXiv preprint arXiv:2202.02948 , 2022

    2022 arXiv

  54. [62]

    Transportation polytope and its applications in parallel server systems

    Sushil Mahavir Varma and Siva Theja Maguluri. Transportation polytope and its applications in parallel server systems. arXiv preprint arXiv:2108.13167 , 2021

    2021 arXiv

  55. [63]

    Poisson arrivals see time averages

    Ronald W Wolff. Poisson arrivals see time averages. Operations research , 30(2):223--231, 1982

    1982

  56. [64]

    Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm

    Yajun Wang and Sam Chiu-wai Wong. Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm. In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP) , pages 1070--1081, 2015

    2015

Pith tools

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