Pith. sign in

REVIEW 3 major objections 3 minor 76 references

Adaptive Approximation Schemes for Matching Queues

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

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

Pith's one-line read Adaptive matching policies can be computed to near-optimal accuracy in polynomial time for constant-size queue networks.

desk verdict A genuine FPTAS/PTAS advance for matching queues, with a few proof details that need fixing before publication. read the letter →

arxiv 2501.08775 v2 pith:4KMLWSKJ submitted 2025-01-15 cs.DS

Alireza AmaniHamedani , Ali Aouad , Amin Saberi This is my paper · ORCID
classification cs.DS MSC 68W2590B2290C4068W27
keywords matchingmarketsMarkovdecisionprocessdriftanalysisonlinealgorithmsapproximationschemesfullypolynomial-timeschemedynamicbipartitequeueing
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

This paper establishes that adaptive matching policies—decisions that use current queue lengths—can be computed to any desired accuracy in polynomial time, for dynamic bipartite matching with abandonment, when the number of supplier types is fixed or the network is Euclidean in fixed dimension. The main contribution is a fully polynomial-time approximation scheme for the bi-criteria problem of minimizing long-run average cost subject to a minimum match rate. The algorithm works by a new hybrid linear program that treats 'short' queues (likely to be empty) with state-dependent variables and 'long' queues (rarely empty) with static variables, then rounds the LP solution online with a priority rule and a bounded virtual buffer. If the theorems are correct, this replaces constant-factor static-policy guarantees with (1−ε)-approximate adaptive policies for these inputs.

What carries the argument

The load-bearing object is the Network LP, a hybrid relaxation combining state-dependent occupancy variables—a dynamic LP per queue with global balance constraints—for queues whose probability of being empty is $\Omega(\varepsilon)$, with static per-type matching variables for queues that are rarely depleted. The companion Priority Rounding algorithm samples a matching assignment from the LP's distribution, always prioritizes short queues, and defers preempted long-queue matches into a virtual buffer; Lemmas 5–8 show the short-queue state converges to the LP's stationary distribution, long queues remain nonempty with probability $1-O(\varepsilon)$, and the buffer remains bounded in expectation. The compression step (Lemmas 3 and 4) is what turns the infinite-dimensional LP into a polynomial-size one: monotone policies are approximated by $K$-bounded policies with $K=O(\frac1\varepsilon(\log\frac{\tau_{\max}}{\tau(\pi)}+\log\frac1\varepsilon))$, by inflating or deflating birth and death rates and coupling stationary distributions.

What would settle it

Exhibit a single-queue instance whose optimal policy has a conditional match rate that strictly decreases at some queue length (violating Definition 1), or a monotone policy for which every $K$-bounded approximation with $K=o(\frac1\varepsilon\log\frac{\tau_{\max}}{\tau})$ loses a constant fraction of throughput—either directly contradicts Lemma 2 or Lemma 3 and would invalidate the FPTAS.

Watch

Extended reading notes

Core claim

The paper's central claim is that the optimal adaptive policy for constant-size matching-queue networks is computationally tractable: for any attainable cost-throughput target $(c^*,\tau^*)$ and any $\varepsilon\in(0,1)$, the algorithm returns a $(1-\varepsilon)$-approximate policy in time $\mathrm{poly}((n/\varepsilon)^{n^2} m^n |I|)$, with a polynomial-time analogue for Euclidean networks of fixed dimension. The argument rests on an exact configuration LP for a single queue, whose dual reveals that optimal policies are threshold policies monotone in queue length, and on a compression lemma showing every monotone policy has a surrogate that bounds queue lengths by $O(\frac1\varepsilon \log\frac{\tau_{\max}}{\tau})$ without losing more than a $(1-\varepsilon)$ factor in throughput. For networks, a hybrid LP separates short and long queues, and the Priority Rounding policy implements its fractional solution online, matching the LP rates up to $O(\varepsilon)$.

Load-bearing premise

Everything rests on the claim that optimal policies are monotone in queue length and that every monotone policy has a logarithmically bounded surrogate; if either fails, the polynomial-size LP no longer approximates the true optimum.

Editorial extensions

If this is right

  • For any fixed number of supplier types, the entire cost-throughput Pareto frontier is approximable within $1\pm\varepsilon$ in time polynomial in the input and $1/\varepsilon$.
  • The single-queue reward-maximization problem, previously known only with a 0.656-approximation, inherits a $(1-\varepsilon)$-approximation scheme from the bi-criteria FPTAS.
  • Applications with a constant number of biological markers (e.g., organ allocation by blood and tissue type) or a fixed spatial dimension (e.g., ride-hailing) obtain computable near-optimal adaptive policies with a simple short/long queue prioritization rule.
  • Euclidean networks of fixed dimension admit an efficient PTAS, implying spatial frictions alone do not force a constant-factor gap between static and adaptive matching.

Reading between the lines

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

  • The short/long dichotomy suggests a transferable two-timescale design principle for stochastic control: state-dependence is only needed where scarcity can bite; abundant resources can be allocated almost statically. The authors note the multivariate birth–death machinery does not extend to non-bipartite graphs, so that transfer is not immediate.
  • A natural testable extension is heterogeneous abandonment rates per supplier type; the authors state the Network LP generalizes trivially, but the rounding analysis—especially the virtual-buffer drift argument—depends on uniform abandonment, so the FPTAS is not known to survive that generalization.
  • One could empirically stress the FPTAS on the same family of 1000 random instances used to demonstrate the adaptivity gap: the algorithm should recover the optimal adaptive DP cost to within $1\pm\varepsilon$, and the gap to static policies of up to 208% should shrink accordingly.
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

3 major / 3 minor

Summary. The paper studies a continuous-time dynamic bipartite matching problem with Poisson supplier arrivals, uniform abandonment, and customers that must be matched upon arrival. The goal is a bi-criteria cost-throughput guarantee: expected long-term average cost at most c* while total match rate is at least τ*. The main result (Theorem 1) is an FPTAS for networks with a constant number of supplier queues, based on a hybrid Network LP that treats 'short' queues with state-dependent variables and 'long' queues with static variables, rounded online by the Priority Rounding policy. Corollary 1 extends this to a PTAS for Euclidean networks of fixed dimension via cell decomposition and clustering. The central technical claims are: exact single-queue Dynamic LP (Lemma 1), bounded-policy approximation for monotone policies (Lemma 3), bounded ℓ in the Network LP (Lemma 4), tracking of short queues (Lemma 5), and stability of virtual buffers (Lemma 7).

Significance. If the proof is completed, the result is significant: it replaces constant-factor static-policy guarantees with near-optimal adaptive policies for a natural class of matching queues with abandonment, and it gives the first (F)PTAS-type results for this model. The hybrid LP relaxation, the short/long queue decomposition, and the virtual-buffer rounding scheme are novel and likely to be influential. The paper is unusually complete in its appendices, with detailed proofs for the single-queue LP, the coupling bound in Lemma 3, the Network LP feasibility reduction, and the Euclidean cell decomposition. However, the proof as written contains a concrete inconsistency in the generator of Lemma 5, and two load-bearing auxiliary claims are either asserted without proof or delegated to an unpublished self-citation; these need to be repaired before the main theorem can be considered established.

major comments (3)
  1. [Appendix B.3, Lemma 5] The displayed intensity matrix has a spurious '+1' in the death rate. For the real short-queue process under Algorithm 1, the transition from ℓ to ℓ−e_i has rate ℓ_i + Σ_M x^ℓ_M γ(M_i) / Σ_M x^ℓ_M, not [Σ_M x^ℓ_M(γ(M_i)+ℓ_i+1)]/Σ_M x^ℓ_M. With the displayed generator, the measure π(ℓ)=Σ_M x^ℓ_M does not satisfy the global balance equation (8): equation (8) has outflow Σ_M x^ℓ_M(γ(M_i)+ℓ_i), not Σ_M x^ℓ_M(γ(M_i)+ℓ_i+1). Consequently the claimed stationary distribution, and therefore equation (14), do not follow as written. The lemma can be repaired by removing the '+1' from Q; with the corrected generator the conclusion does follow from (8). But as written this is a load-bearing gap, since equation (14) is used in Lemma 8, equation (17), equation (18), and the match-rate accounting in Section 3.3.
  2. [Section 3.1] The assertion 'By the pigeonhole principle, there exists κ… such that if we exclude every supplier type with arrival rate in (1/δ^κ, 1/δ^{κ+1}), there exists a policy π with τ(π)≥(1−ε)τ* and c(π)≤c*' is load-bearing because it defines the partition S_short ⊔ S_long and is used in Lemma 4. No proof is provided. The standard empty-interval pigeonhole would require more intervals than supplier types, but the index set has only min{1/ε,n}+1 intervals, which is smaller than n when ε>1/n. The authors should either supply a correct averaging argument over the gaps that accounts for the optimal policy's throughput contribution, or restructure the definition of the gaps so that the removal loss is manifestly O(ε).
  3. [Appendix B.2, Claim 11] The proof of Claim 11 relies on the bound SLP* ≤ c(π*_fr), which is asserted by reference to AmaniHamedani et al. (2024, Claim 2.1), an arXiv self-citation. Claim 11 is needed for Lemma 4 in the small-throughput regime τ* ≤ ε²/n, and Lemma 4 is in turn used in the proof of Theorem 1. This is a load-bearing external dependency. Please provide a self-contained proof of the static-LP relaxation, or state and prove the precise version of the cited claim in the appendix.
minor comments (3)
  1. [Appendix B.3] The transition ℓ → ℓ−e_i in the intensity matrix should be restricted to states with ℓ_i ≥ 1; as written the generator is described for all distinct states but includes invalid downward transitions from ℓ_i = 0.
  2. [Section 3.1] In the sentence 'we distinguish between two types of customer types C = C^{ct} ⊔ C^{ct}', the two sets are not visually distinguishable in the text. Please use distinct symbols such as C^{ct} and C^{cr} (or C^{contentious} and C^{non-contentious}) consistently through equations (13) and Lemma 8.
  3. [Section 1.2] The notation λ and λ̄ for the short/long cutoff values in Section 3.1 conflicts with the use of λ_i for supplier arrival rates; consider renaming the cutoffs (for example L and ̄L) to avoid confusion.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the LP is a genuine occupancy-measure reformulation; the only load-bearing self-citation is a minor corner-case reference.

full rationale

The derivation is not circular. The DLP and NLP are occupancy-measure linear programs: the variables are defined as steady-state probabilities of (state, matching-set) pairs, and the constraints are the detailed or global balance equations of the induced birth-death processes. Lemma 1 proves both directions (any policy yields a feasible occupancy vector; any feasible vector is realized by the natural stationary policy), so DLP is an exact reformulation rather than a fit. Lemma 3's bounded-policy compression is a self-contained coupling argument (Appendix A.6), and the Priority Rounding analysis derives long-queue rates from drift and coupling lemmas (Lemmas 6-8) rather than from the LP solution. The only overlapping-author citation in a load-bearing role appears in Claim 11 (Appendix B.2), where the validity of the static LP (SLP) is referred to AmaniHamedani et al. (2024, Claim 2.1). That is a real theorem from a separate paper; it does not depend on the present FPTAS, and it is used only in the corner case tau* <= eps^2/n, so it is a minor self-citation rather than circularity. A verification concern, as opposed to circularity: the proof of Lemma 5 (Appendix B.3) asserts the intensity matrix Q for the short-queue process rather than deriving it from Algorithm 1; the displayed death rate contains (gamma(M_i)+ell_i+1), while the algorithm's death rate would be the abandonment rate ell_i plus the match rate gamma(M_i). If this is an error, Lemma 5 would be unproven, but that is a correctness gap, not a reduction of a prediction to its input by construction. The central FPTAS derivation remains structurally independent.

Assumptions & free parameters 1 free parameters · 6 assumptions · 1 invented entities

The model is a Markovian queueing system; nonstandard assumptions are either standard stochastic-process facts or explicitly simplifying model choices. The main ad hoc step is the short/long rate-gap WLOG, and the static LP in Claim 11 is self-cited. No physical entities are postulated; the virtual buffer is bookkeeping.

free parameters (1)
  • kappa and induced short/long thresholds lambda=1/delta^kappa, bar-lambda=1/delta^(kappa+1), with delta=epsilon^2/n
    Introduced in Section 3.1 to separate short from long queues. The existence of a good kappa is by pigeonhole enumeration, but the proof assumes the target remains attainable after deleting mid-rate types. This is an algorithmic design choice, not a data fit.
assumptions (6)
  • domain assumption Supplier arrivals are Poisson, abandonment is exponential at common rate mu normalized to 1, customers arrive by independent Poisson processes and must be matched or lost at arrival.
    Model in Section 1; all theorems are conditional on this Markovian queueing model. Heterogeneous abandonment is explicitly excluded in Section 5.
  • standard math PASTA and Poisson thinning hold for the stationary analysis and for the coupled and fake arrival processes.
    Used in Lemma 1, in transition-rate derivations in Appendix A.1, and in Lemma 7 for increment and decrement rates.
  • standard math Strong duality for the infinite-dimensional dynamic LP holds via the transversality condition delta_l to 0.
    Invoked in Section 2.1 before Lemma 2, citing Romeijn et al. (1992). This is background LP duality in infinite dimensions.
  • ad hoc to paper The target (c*,tau*) remains attainable after deleting supplier types whose rates fall in the selected geometric gap.
    Section 3.1 states that (c*,tau*) is still attainable after removal of these supplier types; the paper says this avoids carrying a (1+epsilon) factor but does not prove it.
  • domain assumption The static LP (SLP) is a valid relaxation of the frequent-queue subproblem in the small-throughput case.
    Claim 11 in Appendix B.2 refers to AmaniHamedani et al. (2024, Claim 2.1) for the proof; this is a result from overlapping authors rather than derived in this paper.
  • standard math Standard stochastic-stability facts: Foster-Lyapunov drift results and Markov-modulated M/M/1 matrix-geometric stationarity.
    Used in Claim 18 and Lemma 7 to bound auxiliary queues and the virtual buffer. Cited to Hajek (2015) and Neuts (1978, 1994).
invented entities (1)
  • Virtual buffer V_{i,j}
    purpose: Bookkeeping device that delays matches between long queues and contentious customer types so that the priority-rounding policy tracks the Network LP's long-queue match rates.
    Pure algorithmic state variable, not a physical entity. Bounded expectation is proved via drift and matrix-geometric stability in Lemma 7.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Adaptive Approximation Schemes for Matching Queues." pith.science (2026). https://pith.science/paper/4KMLWSKJ

@misc{pith2026250108775,
  author       = {Pith},
  title        = {Pith review of: Adaptive Approximation Schemes for Matching Queues},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4KMLWSKJ}},
  note         = {Machine review of arXiv:2501.08775}
}
abstract

We study a continuous-time, infinite-horizon dynamic bipartite matching problem. Suppliers arrive according to a Poisson process; while waiting, they may abandon the queue at a uniform rate. Customers on the other hand must be matched upon arrival. The objective is to minimize the expected long-term average cost subject to a throughput constraint on the total match rate. Previous literature on dynamic matching focuses on "static" policies, where the matching decisions do not depend explicitly on the state of the supplier queues, achieving constant-factor approximations. By contrast, we design "adaptive" policies, which leverage queue length information, and obtain near-optimal polynomial-time algorithms for several classes of instances. First, we develop a bi-criteria fully polynomial-time approximation scheme for dynamic matching on networks with a constant number of queues--that computes a $(1-\epsilon)$-approximation of the optimal policy in time polynomial in both the input size and $1/\epsilon$. A key new technique is a hybrid LP relaxation, which combines static and state-dependent LP approximations of the queue dynamics, after a decomposition of the network. Networks with a constant number of queues are motivated by deceased organ donation schemes, where the supply types can be divided according to blood and tissue types. The above algorithm, combined with a careful cell decomposition gives an efficient polynomial-time approximation scheme for dynamic matching on Euclidean networks of fixed dimension. The Euclidean case is of interest in ride-hailing and spatial service platforms, where the goal is to fulfill as many trips as possible while minimizing driving distances.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

76 extracted references · 62 canonical work pages

  1. [1]

    , " * write output.state after.block = add.period write newline

    ENTRY address author booktitle chapter doi edition editor eid howpublished institution isbn issn journal key month note number organization pages publisher school series title type url volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all := #1...

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in "" FUNCTION format.date year ...

  3. [3]

    A., Somaini, P., and Waldinger, D

    Agarwal, N., Ashlagi, I., Rees, M. A., Somaini, P., and Waldinger, D. (2021). Equilibrium allocations under alternative waitlist designs: Evidence from deceased donor kidneys. Econometrica , 89(1):37--76

    work page 2021

  4. [4]

    and Devanur, N

    Agrawal, S. and Devanur, N. R. (2014). Fast algorithms for online stochastic convex programming. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms , pages 1405--1424. SIAM

    work page 2014

  5. [5]

    Akbarpour, M., Li, S., and Gharan, S. O. (2020). Thickness and information in dynamic matching markets. Journal of Political Economy , 128(3):783--815

    2020

  6. [6]

    Altman, E. (2021). Constrained Markov decision processes . Routledge

    work page 2021

  7. [7]

    AmaniHamedani, A., Aouad, A., and Freund, D. (2023). Spatial matching under multihoming. Available at SSRN 4488342

    work page 2023

  8. [8]

    AmaniHamedani, A., Aouad, A., Pollner, T., and Saberi, A. (2024). Improved approximations for stationary bipartite matching: Beyond probabilistic independence. arXiv preprint arXiv:2411.08218

    arXiv 2024

Show all 76 references
  1. [9]

    Anari, N., Niazadeh, R., Saberi, A., and Shameli, A. (2019). Nearly optimal pricing algorithms for production constrained and laminar bayesian selection. In Proceedings of the 2019 ACM Conference on Economics and Computation , pages 91--92

    2019

  2. [10]

    and Sar ta c , \"O

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

    2022

  3. [11]

    and Gurvich, I

    Arlotto, A. and Gurvich, I. (2019). Uniformly bounded regret in the multisecretary problem. Stochastic Systems , 9(3):231--260

    2019

  4. [12]

    and Ma, W

    Arnosti, N. and Ma, W. (2023). Tight guarantees for static threshold policies in the prophet secretary problem. Operations research , 71(5):1777--1788

    2023

  5. [13]

    Ashlagi, I., Burq, M., Dutta, C., Jaillet, P., Saberi, A., and Sholley, C. (2023). Edge-weighted online windowed matching. Math. Oper. Res. , 48(2):999--1016

    2023

  6. [14]

    Ashlagi, I., Leshno, J., Qian, P., and Saberi, A. (2022). Price discovery in waiting lists. Available at SSRN 4192003

    2022

  7. [15]

    Aveklouris, A., DeValve, L., Stock, M., and Ward, A. (2024). Matching impatient and heterogeneous demand and supply. Operations Research

    2024

  8. [16]

    Begeot, J., Marcovici, I., and Moyal, P. (2023). Stability regions of systems with compatibilities and ubiquitous measures on graphs. Queueing Systems , 103(3):275--312

    2023

  9. [17]

    and Tsitsiklis, J

    Bertsimas, D. and Tsitsiklis, J. N. (1997). Introduction to linear optimization , volume 6. Athena scientific Belmont, MA

    1997

  10. [18]

    Castillo, J. C. (2023). Who benefits from surge pricing? Available at SSRN 3245533

    2023

  11. [19]

    C., Knoepfle, D., and Weyl, E

    Castillo, J. C., Knoepfle, D., and Weyl, E. G. (2024). Matching and pricing in ride hailing: Wild goose chases and how to solve them. Management Science

    2024

  12. [20]

    Castro, F., Nazerzadeh, H., and Yan, C. (2020). Matching queues with reneging: a product form solution. Queueing Systems , 96(3):359--385

    2020

  13. [21]

    Collina, N., Immorlica, N., Leyton-Brown, K., Lucier, B., and Newman, N. (2020). 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, Proceedings...

    2020

  14. [22]

    C., Goemans, M

    Dean, B. C., Goemans, M. X., and Vondr \'a k, J. (2005). Adaptivity and approximation for stochastic packing problems. In SODA , volume 5, pages 395--404

    2005

  15. [23]

    Devanur, N. R. and Hayes, T. P. (2009). The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM conference on Electronic commerce , pages 71--78

    2009

  16. [24]

    R., Jain, K., and Kleinberg, R

    Devanur, N. R., Jain, K., and Kleinberg, R. D. (2013). Randomized primal-dual analysis of ranking for online bipartite matching. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms , pages 101--107. SIAM

    2013

  17. [25]

    R., Jain, K., Sivan, B., and Wilkens, C

    Devanur, N. R., Jain, K., Sivan, B., and Wilkens, C. A. (2011). Near optimal online algorithms and fast approximation algorithms for resource allocation problems. In Proceedings of the 12th ACM conference on Electronic commerce , pages 29--38

    2011

  18. [26]

    D \"u tting, P., Gergatsouli, E., Rezvan, R., Teng, Y., and Tsigonias-Dimitriadis, A. (2023). Prophet secretary against the online optimal. In Proceedings of the 24th ACM Conference on Economics and Computation , pages 561--581

    2023

  19. [27]

    Echenique, F., Immorlica, N., and Vazirani, V. V. (2023). Online and matching-based market design. Technical report, Cambridge University Press

    2023

  20. [28]

    Ezra, T., Feldman, M., Gravin, N., and Tang, Z. G. (2022). Prophet matching with general arrivals. Mathematics of Operations Research , 47(2):878--898

    2022

  21. [29]

    Fahrbach, M., Huang, Z., Tao, R., and Zadimoghaddam, M. (2022). Edge-weighted online bipartite matching. Journal of the ACM , 69(6):1--35

    2022

  22. [30]

    S., and Stein, C

    Feldman, J., Henzinger, M., Korula, N., Mirrokni, V. S., and Stein, C. (2010). Online stochastic packing applied to display ad allocation. In European Symposium on Algorithms , pages 182--194. Springer

    2010

  23. [31]

    Feldman, J., Mehta, A., Mirrokni, V., and Muthukrishnan, S. (2009). Online stochastic matching: Beating 1-1/e. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science , pages 117--126. IEEE

    2009

  24. [32]

    and Righter, R

    Gardner, K. and Righter, R. (2020). Product forms for FCFS queueing models with arbitrary server-job compatibilities: an overview. Queueing Systems , 96(1):3--51

    2020

  25. [33]

    Gentry, S. E. and Segev, D. (2015). The best-laid schemes of mice and men often go awry; how should we repair them? American Journal of Transplantation , 15(10):2539--2540

    2015

  26. [34]

    Grosof, I., Hong, Y., and Harchol-Balter, M. (2024). Analysis of markovian arrivals and service with applications to intermittent overload. arXiv preprint arXiv:2405.04102

    2024 arXiv

  27. [35]

    Gupta, A., Guruganesh, G., Peng, B., and Wajc, D. (2019). Stochastic online metric matching. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 , page 67

    2019

  28. [36]

    and Molinaro, M

    Gupta, A. and Molinaro, M. (2016). How the experts algorithm can help solve LP s online. Mathematics of Operations Research , 41(4):1404--1431

    2016

  29. [37]

    Gupta, V. (2024). Greedy algorithm for multiway matching with bounded regret. Operations Research , 72(3):1139--1155

    2024

  30. [38]

    Hajek, B. (2015). Random processes for engineers . Cambridge university press

    2015

  31. [39]

    G., Wu, X., Zhang, Y., and Zhu, X

    Huang, Z., Kang, N., Tang, Z. G., Wu, X., Zhang, Y., and Zhu, X. (2018). How to match when all vertices arrive online. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of computing , pages 17--29

    2018

  32. [40]

    G., Tao, R., Wu, X., and Zhang, Y

    Huang, Z., Peng, B., Tang, Z. G., Tao, R., Wu, X., and Zhang, Y. (2019). Tight competitive ratios of classic matching algorithms in the fully online model. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 2875--2886. SIAM

    2019

  33. [41]

    and Shu, X

    Huang, Z. and Shu, X. (2021). Online stochastic matching, poisson arrivals, and the natural linear program. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 682--693

    2021

  34. [42]

    Huang, Z., Shu, X., and Yan, S. (2022). The power of multiple choices in online stochastic matching. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 91--103

    2022

  35. [43]

    G., and Wajc, D

    Huang, Z., Tang, Z. G., and Wajc, D. (2024). Online matching: A brief survey. ACM SIGecom Exchanges , 22(1):135--158

    2024

  36. [44]

    G., Wu, X., and Zhang, Y

    Huang, Z., Tang, Z. G., Wu, X., and Zhang, Y. (2020a). 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

  37. [45]

    Huang, Z., Zhang, Q., and Zhang, Y. (2020b). Adwords in a panorama. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 1416--1426. IEEE

    2020

  38. [46]

    M., and Maguluri, S

    Hurtado-Lange, D., Varma, S. M., and Maguluri, S. T. (2022). Logarithmic heavy traffic error bounds in generalized switch and load balancing systems. Journal of Applied Probability , 59(3):652--669

    2022

  39. [47]

    Jonckheere, M., Moyal, P., Ram \' rez, C., and Soprano-Loto, N. (2023). Generalized max-weight policies in stochastic matching. Stochastic Systems , 13(1):40--58

    2023

  40. [48]

    Kallenberg, O. (2002). Foundations of modern probability . Springer. Second edition

    2002

  41. [49]

    Kanoria, Y. (2022). Dynamic spatial matching. In Proceedings of the 23rd ACM Conference on Economics and Computation , pages 63--64

    2022

  42. [50]

    M., Vazirani, U

    Karp, R. M., Vazirani, U. V., and Vazirani, V. V. (1990). An optimal algorithm for on-line bipartite matching. In Proceedings of the twenty-second annual ACM symposium on Theory of computing , pages 352--358

    1990

  43. [51]

    Kelly, F. P. (2011). Reversibility and stochastic networks . Cambridge University Press

    2011

  44. [52]

    Kerimov, S., Ashlagi, I., and Gurvich, I. (2023). On the optimality of greedy policies in dynamic matching. Operations Research

    2023

  45. [53]

    Kerimov, S., Ashlagi, I., and Gurvich, I. (2024). Dynamic matching: Characterizing and achieving constant regret. Management Science , 70(5):2799--2822

    2024

  46. [54]

    Kessel, K., Shameli, A., Saberi, A., and Wajc, D. (2022). The stationary prophet inequality problem. In Proceedings of the 23rd ACM Conference on Economics and Computation , pages 243--244

    2022

  47. [55]

    o nnis, A., Radke, K., and V \

    Kesselheim, T., T \"o nnis, A., Radke, K., and V \"o cking, B. (2014). Primal beats dual on online packing LP s in the random-order model. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages 303--312

    2014

  48. [56]

    Kohlenberg, A. (2024). Greedy matching of impatient agents: The role of inventory. SSRN Electronic Journal . Available at SSRN: https://ssrn.com/abstract=4804794

    2024

  49. [57]

    and Gurvich, I

    Kohlenberg, A. and Gurvich, I. (2024). The cost of impatience in dynamic matching: Scaling laws and operating regimes. Management Science

    2024

  50. [58]

    H., Gharan, S

    Manshadi, V. H., Gharan, S. O., and Saberi, A. (2012). Online stochastic matching: Online actions based on offline statistics. Mathematics of Operations Research , 37(4):559--573

    2012

  51. [59]

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

    2007

  52. [60]

    Moyal, P., Busic, A., and Mairesse, J. (2023). On the sub-additivity of stochastic matching. arXiv preprint arXiv:2305.00187

    2023 arXiv

  53. [61]

    and Stolyar, A

    Nazari, M. and Stolyar, A. L. (2019). Reward maximization in general dynamic matching systems. Queueing Systems , 91:143--170

    2019

  54. [62]

    Neely, M. (2022). Stochastic network optimization with application to communication and queueing systems . Springer Nature

    2022

  55. [63]

    Neuts, M. F. (1978a). Further results on the M / M /1 queue with randomly varying rates. Opsearch , 15(4):158

    1978

  56. [64]

    Neuts, M. F. (1978b). The M / M /1 queue with randomly varying arrival and service rates. Opsearch , 15:139--157

    1978

  57. [65]

    Neuts, M. F. (1994). Matrix-geometric solutions in stochastic models: an algorithmic approach . Courier Corporation

    1994

  58. [66]

    and Ward, A

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

    2020

  59. [67]

    and Wajc, D

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

    2024

  60. [68]

    Romeijn, H. E. and Smith, R. L. (1998). Shadow prices in infinite-dimensional linear programming. Mathematics of operations research , 23(1):239--256

    1998

  61. [69]

    E., Smith, R

    Romeijn, H. E., Smith, R. L., and Bean, J. C. (1992). Duality in infinite dimensional linear programming. Mathematical programming , 53(1):79--97

    1992

  62. [70]

    Schrijver, A. (2003). Combinatorial optimization: polyhedra and efficiency . Springer

    2003

  63. [71]

    Segev, D. (2024). Near-optimal adaptive policies for serving stochastically departing customers. Operations Research

    2024

  64. [72]

    M., Bumpensanti, P., Maguluri, S

    Varma, S. M., Bumpensanti, P., Maguluri, S. T., and Wang, H. (2023). Dynamic pricing and matching for two-sided queues. Operations Research , 71(1):83--100

    2023

  65. [73]

    Wang, G., Zhang, H., and Zhang, J. (2024). On-demand ride-matching in a spatial model with abandonment and cancellation. Operations Research , 72(3):1278--1297

    2024

  66. [74]

    Wei, Y., Xu, J., and Yu, S. H. (2023). Constant regret primal-dual policy for multi-way dynamic matching. In Abstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems , pages 79--80

    2023

  67. [75]

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

    1982

  68. [76]

    and Guo, X

    Zhang, L. and Guo, X. (2008). Constrained continuous-time markov decision processes with average criteria. Mathematical Methods of Operations Research , 67(2):323--340

    2008

Pith tools

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