pith. sign in

arxiv: 2606.05546 · v1 · pith:WVRL7AIRnew · submitted 2026-06-04 · 💻 cs.DS · cs.GT

Online Min-Cost Matching with General Arrivals

Josh Ascher , Eric Balkanski , Jason Chatzitheodorou , Vasilis Gkatzelis This is my paper

Pith reviewed 2026-06-27 23:45 UTC · model grok-4.3

classification 💻 cs.DS cs.GT
keywords online min-cost matchinggeneral arrivalscompetitive ratioadversarial modelrandom order modeli.i.d. arrivalsunknown distribution
0
0 comments X

The pith

In online min-cost perfect matching where all participants arrive online, any algorithm has unbounded competitive ratio under adversarial and random-order arrivals, but an O(log² n) ratio holds for unknown i.i.d. arrivals.

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

The paper examines online min-cost perfect matching in a general-arrivals setting where every participant arrives dynamically and must either match to someone in a waiting pool or join the pool. It establishes that no algorithm achieves a bounded competitive ratio in the adversarial model or the random-order model. For arrivals drawn i.i.d. from a fixed but unknown distribution, however, the authors supply an algorithm whose ratio is O(log² n). This yields a separation between what is possible in random-order versus unknown-i.i.d. models. The distinction matters because many matching applications, such as ride-sharing, have participants arriving on both sides rather than one side remaining static.

Core claim

In the online min-cost perfect-matching problem with general arrivals, where all participants arrive online and decide upon arrival whether to match immediately or join a waiting pool, the competitive ratio of any algorithm is unbounded in both the adversarial and random-order input models. In contrast, when arrivals are i.i.d. from an unknown distribution, an O(log² n)-competitive algorithm exists.

What carries the argument

The input model (adversarial, random-order, or i.i.d.) as the factor that determines whether bounded competitive ratios are achievable for symmetric online min-cost matching.

If this is right

  • No algorithm can guarantee a finite competitive ratio against adversarial arrivals.
  • The same unboundedness holds for random-order arrivals.
  • An O(log² n) competitive ratio is achievable when arrivals are i.i.d. from an unknown distribution.
  • A separation exists between the competitive ratios attainable in the random-order model versus the unknown-i.i.d. model.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Systems may need to shape or verify arrival patterns to approximate i.i.d. behavior before bounded guarantees apply.
  • Randomness in arrival order alone does not suffice for good ratios when both sides of the match are dynamic.
  • The separation invites checking whether other online problems with symmetric participants exhibit the same model gap.

Load-bearing premise

Arrivals are drawn independently from a fixed but unknown distribution.

What would settle it

An adversarial sequence of arrivals for which every online algorithm produces total cost that grows unbounded relative to the optimal offline matching cost.

read the original abstract

In the classic online min-cost matching problem, the goal is to match a sequence of requests that arrive dynamically over time to a set of static servers, aiming to minimize the total cost of the matching. This assumes that there are two distinct "sides" and that only one of these sides arrives online, but many of the motivating applications violate these assumptions. We study online min-cost perfect-matching when \emph{all} participants arrive online and, upon arrival, they need to either be matched to someone from a waiting pool or to join the waiting pool. We evaluate the competitive ratios achievable in different input models and show that for both the adversarial and the random-order input models the competitive ratio of any algorithm is unbounded. In contrast, for i.i.d. arrivals we give a $O( \log^2{n})$-competitive algorithm, even if the distribution that generates these arrivals is unknown to the algorithm. This result implies a rare example of separation in the achievable competitive ratio between the random-order and the unknown-i.i.d. input models.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper studies the online min-cost perfect matching problem in which all participants arrive online and, upon arrival, must either be matched to an element of the current waiting pool or join the pool themselves. It establishes that no algorithm achieves a bounded competitive ratio in the adversarial or random-order arrival models. In contrast, for arrivals drawn i.i.d. from an unknown distribution it presents an O(log² n)-competitive algorithm that does not require knowledge of the distribution. The result is positioned as a separation between the random-order and unknown-i.i.d. models.

Significance. If the stated bounds and algorithm hold, the work supplies a rare explicit separation between the random-order and unknown-i.i.d. input models in competitive analysis. The fact that the O(log² n) guarantee is obtained without distributional knowledge strengthens its relevance to applications where the arrival process is only partially known.

minor comments (1)
  1. The abstract states the main results but does not indicate the high-level technique (e.g., potential function, primal-dual, or sampling) used to obtain the O(log² n) bound; a single sentence would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading, the positive significance assessment, and the recommendation to accept. The report correctly summarizes our main results on the separation between input models.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper states competitive-ratio separations across input models (unbounded for adversarial/random-order; O(log² n) for unknown i.i.d.) via standard competitive analysis against an external OPT benchmark. No equations, parameter fits, or self-citations appear in the provided text that reduce any claimed result to a definition or input by construction. The i.i.d. algorithm is asserted to operate without distribution knowledge, which is an independent algorithmic claim rather than a renaming or self-referential fit. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard assumptions in online algorithm theory without introducing new free parameters or entities.

axioms (1)
  • standard math Standard definitions of competitive ratio in online algorithms
    Used to evaluate algorithm performance against optimal offline solution.

pith-pipeline@v0.9.1-grok · 5719 in / 1079 out tokens · 22456 ms · 2026-06-27T23:45:19.158334+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

62 extracted references · 17 canonical work pages

  1. [1]

    , title =

    Filos-Ratsikas, Aris and Gkatzelis, Vasilis and Latifian, Mohamad and Rewinski, Emma and Voudouris, Alexandros A. , title =. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence , articleno =. 2025 , isbn =

    2025

  2. [2]

    Proceedings of the 24th ACM Conference on Economics and Computation , pages =

    Anari, Nima and Charikar, Moses and Ramakrishnan, Prasanna , title =. Proceedings of the 24th ACM Conference on Economics and Computation , pages =. 2023 , isbn =

    2023

  3. [3]

    Truthful Facility Assignment with Resource Augmentation: An Exact Analysis of Serial Dictatorship

    Ioannis Caragiannis and Aris Filos-Ratsikas and Frederiksen, S ren Kristoffer Stiil and Hansen, Kristoffer Arnsfelt and Zihan Tan. Truthful Facility Assignment with Resource Augmentation: An Exact Analysis of Serial Dictatorship. Mathematical Programming, Series B. 2024

    2024

  4. [4]

    17th Innovations in Theoretical Computer Science Conference (ITCS 2026) , pages=

    Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion , author=. 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) , pages=. 2026 , organization=

    2026

  5. [5]

    1994 , issn =

    On-line algorithms for weighted bipartite matching and stable marriages , journal =. 1994 , issn =. doi:https://doi.org/10.1016/0304-3975(94)90042-6 , author =

    work page doi:10.1016/0304-3975(94)90042-6 1994

  6. [6]

    1993 , issn =

    Online Weighted Matching , journal =. 1993 , issn =. doi:https://doi.org/10.1006/jagm.1993.1026 , author =

    work page doi:10.1006/jagm.1993.1026 1993

  7. [7]

    Online algorithms: The state of the art , pages=

    On-line network optimization problems , author=. Online algorithms: The state of the art , pages=. 2005 , publisher=

    2005

  8. [8]

    The Online Metric Matching Problem for Doubling Metrics , booktitle =

    Anupam Gupta and Kevin Lewi , editor =. The Online Metric Matching Problem for Doubling Metrics , booktitle =

  9. [9]

    34th International Symposium on Computational Geometry (SoCG 2018) , pages=

    Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line , author=. 34th International Symposium on Computational Geometry (SoCG 2018) , pages=. 2018 , organization=

    2018

  10. [10]

    Proceedings of the 24th ACM Conference on Economics and Computation , pages=

    The power of greedy for online minimum cost matching on the line , author=. Proceedings of the 24th ACM Conference on Economics and Computation , pages=

  11. [11]

    Theoretical Computer Science , volume=

    Online matching on a line , author=. Theoretical Computer Science , volume=. 2005 , publisher=

    2005

  12. [12]

    International Workshop on Approximation and Online Algorithms , pages=

    The online matching problem on a line , author=. International Workshop on Approximation and Online Algorithms , pages=. 2003 , organization=

    2003

  13. [13]

    2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    An input sensitive online algorithm for the metric bipartite matching problem , author=. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2017 , organization=

    2017

  14. [14]

    Algorithmica , volume=

    A o(n) -Competitive Deterministic Algorithm for Online Matching on a Line , author=. Algorithmica , volume=. 2019 , publisher=

    2019

  15. [15]

    ACM Trans

    Peserico, Enoch and Scquizzato, Michele , title =. ACM Trans. Algorithms , month = jul, articleno =. 2023 , issue_date =. doi:10.1145/3594873 , abstract =

    work page doi:10.1145/3594873 2023

  16. [16]

    2022 , eprint=

    Empirical Optimal Transport between Different Measures Adapts to Lower Complexity , author=. 2022 , eprint=

    2022

  17. [17]

    Mathematics of Operations Research , author =

    Prophet. Mathematics of Operations Research , author =. 2022 , pages =. doi:10.1287/moor.2021.1152 , abstract =

    work page doi:10.1287/moor.2021.1152 2022

  18. [18]

    International Colloquium on Automata, Languages, and Programming , pages=

    Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm , author=. International Colloquium on Automata, Languages, and Programming , pages=. 2015 , organization=

    2015

  19. [19]

    SIGecom Exch

    Huang, Zhiyi and Tang, Zhihao Gavin and Wajc, David , title =. SIGecom Exch. , month = oct, pages =. 2024 , issue_date =. doi:10.1145/3699824.3699837 , abstract =

    work page doi:10.1145/3699824.3699837 2024

  20. [20]

    Blum, Avrim and Sandholm, Tuomas and Zinkevich, Martin , title =. J. ACM , month = sep, pages =. 2006 , issue_date =. doi:10.1145/1183907.1183913 , abstract =

    work page doi:10.1145/1183907.1183913 2006

  21. [21]

    Huang, Zhiyi and Kang, Ning and Tang, Zhihao Gavin and Wu, Xiaowei and Zhang, Yuhao and Zhu, Xue , title =. J. ACM , month = may, articleno =. 2020 , issue_date =. doi:10.1145/3390890 , abstract =

    work page doi:10.1145/3390890 2020

  22. [22]

    2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Online matching with general arrivals , author=. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2019 , organization=

    2019

  23. [23]

    Online algorithms for maximum cardinality matching with edge arrivals

    Buchbinder, Niv and Segev, Danny and Tkach, Yevgeny. Online algorithms for maximum cardinality matching with edge arrivals. Algorithmica

  24. [24]

    Aranyak Mehta , title =. Found. Trends Theor. Comput. Sci. , volume =

  25. [25]

    Proceedings of the 25th ACM Conference on Economics and Computation , pages=

    Improved bounds for fractional online matching problems , author=. Proceedings of the 25th ACM Conference on Economics and Computation , pages=

  26. [26]

    Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing , pages =

    Karande, Chinmay and Mehta, Aranyak and Tripathi, Pushkar , title =. Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing , pages =. 2011 , isbn =. doi:10.1145/1993636.1993715 , abstract =

    work page doi:10.1145/1993636.1993715 2011

  27. [27]

    Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing , pages =

    Mahdian, Mohammad and Yan, Qiqi , title =. Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing , pages =. 2011 , isbn =. doi:10.1145/1993636.1993716 , abstract =

    work page doi:10.1145/1993636.1993716 2011

  28. [28]

    and Hayes, Thomas P

    Devanur, Nikhil R. and Hayes, Thomas P. , title =. Proceedings of the 10th ACM Conference on Electronic Commerce , pages =. 2009 , isbn =. doi:10.1145/1566374.1566384 , abstract =

    work page doi:10.1145/1566374.1566384 2009

  29. [29]

    ACM Trans

    Huang, Zhiyi and Tang, Zhihao Gavin and Wu, Xiaowei and Zhang, Yuhao , title =. ACM Trans. Algorithms , month = jun, articleno =. 2019 , issue_date =. doi:10.1145/3326169 , abstract =

    work page doi:10.1145/3326169 2019

  30. [30]

    Williamson , title =

    Billy Jin and David P. Williamson , title =. CoRR , volume =. 2020 , eprinttype =. 2007.12823 , timestamp =

    arXiv 2020

  31. [31]

    o nnis, Andreas and V \

    Kesselheim, Thomas and Radke, Klaus and T \"o nnis, Andreas and V \"o cking, Berthold. An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions. Algorithms -- ESA 2013. 2013

    2013

  32. [32]

    CoRR , volume =

    Nitish Korula and Martin Pal , title =. CoRR , volume =. 2008 , eprinttype =. 0807.1139 , timestamp =

    Pith/arXiv arXiv 2008

  33. [33]

    Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

    Kleinberg, Robert , title =. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. 2005 , isbn =

    2005

  34. [34]

    Proceedings of the 23rd ACM Conference on Economics and Computation , pages =

    Kanoria, Yash , title =. Proceedings of the 23rd ACM Conference on Economics and Computation , pages =. 2022 , isbn =. doi:10.1145/3490486.3538278 , abstract =

    work page doi:10.1145/3490486.3538278 2022

  35. [35]

    Stochastic Online Metric Matching , booktitle =

    Anupam Gupta and Guru Guruganesh and Binghui Peng and David Wajc , editor =. Stochastic Online Metric Matching , booktitle =

  36. [36]

    and Komlós, J

    Ajtai, M. and Komlós, J. and Tusnády, G. , year =. On optimal matchings , volume =. Combinatorica , publisher =. doi:10.1007/bf02579135 , number =

    work page doi:10.1007/bf02579135

  37. [37]

    Probability theory of classical euclidean optimization problems

    Yukich, Joseph E. Probability theory of classical euclidean optimization problems

  38. [38]

    2024 , eprint=

    Stochastic Online Metric Matching: Adversarial is no Harder than Stochastic , author=. 2024 , eprint=

    2024

  39. [39]

    Theory of Computing Systems , volume=

    Deterministic min-cost matching with delays , author=. Theory of Computing Systems , volume=. 2020 , publisher=

    2020

  40. [40]

    Theory of Computing Systems , volume=

    Online matching with delays and stochastic arrival times , author=. Theory of Computing Systems , volume=. 2025 , publisher=

    2025

  41. [41]

    arXiv preprint arXiv:2502.16862 , year=

    Potential-Based Greedy Matching for Dynamic Delivery Pooling , author=. arXiv preprint arXiv:2502.16862 , year=

    arXiv

  42. [42]

    A Primal-Dual Online Deterministic Algorithm for Matching with Delays

    Bienkowski, Marcin and Kraska, Artur and Liu, Hsiang-Hsuan and Schmidt, Pawe. A Primal-Dual Online Deterministic Algorithm for Matching with Delays. Approximation and Online Algorithms. 2018

    2018

  43. [43]

    2016 , isbn =

    Emek, Yuval and Kutten, Shay and Wattenhofer, Roger , title =. 2016 , isbn =. doi:10.1145/2897518.2897557 , booktitle =

    work page doi:10.1145/2897518.2897557 2016

  44. [44]

    1979 , issn =

    The tail of the hypergeometric distribution , journal =. 1979 , issn =. doi:https://doi.org/10.1016/0012-365X(79)90084-0 , author =

    work page doi:10.1016/0012-365x(79)90084-0 1979

  45. [45]

    International Colloquium on Automata, Languages, and Programming , pages=

    The online metric matching problem for doubling metrics , author=. International Colloquium on Automata, Languages, and Programming , pages=. 2012 , organization=

    2012

  46. [46]

    Journal of Scheduling , volume=

    A randomized algorithm for the on-line weighted bipartite matching problem , author=. Journal of Scheduling , volume=. 2008 , publisher=

    2008

  47. [47]

    ACM Transactions on Algorithms , volume=

    Matching on the line admits no-competitive algorithm , author=. ACM Transactions on Algorithms , volume=. 2023 , publisher=

    2023

  48. [48]

    Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm , pages=

    Randomized online algorithms for minimum metric bipartite matching , author=. Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm , pages=

  49. [49]

    ACM SIGecom Exchanges , volume=

    Online matching: A brief survey , author=. ACM SIGecom Exchanges , volume=. 2024 , publisher=

    2024

  50. [50]

    Proceedings of the forty-third annual ACM symposium on Theory of computing , pages=

    Online bipartite matching with unknown distributions , author=. Proceedings of the forty-third annual ACM symposium on Theory of computing , pages=

  51. [51]

    Approximation, Randomization, and Combinatorial Optimization

    A robust and optimal online algorithm for minimum metric bipartite matching , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) , pages=. 2016 , organization=

    2016

  52. [52]

    Operations Research , volume=

    Online metric matching: Beyond the worst case , author=. Operations Research , volume=. 2026 , publisher=

    2026

  53. [53]

    The Annals of Applied Probability , volume=

    Dynamic spatial matching , author=. The Annals of Applied Probability , volume=. 2025 , publisher=

    2025

  54. [54]

    Approximation, Randomization, and Combinatorial Optimization

    Online minimum cost matching with recourse on the line , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) , pages=. 2020 , organization=

    2020

  55. [55]

    Proceedings of the 23rd ACM Conference on Economics and Computation , pages =

    Akbarpour, Mohammad and Alimohammadi, Yeganeh and Li, Shengwu and Saberi, Amin , title =. Proceedings of the 23rd ACM Conference on Economics and Computation , pages =. 2022 , isbn =. doi:10.1145/3490486.3538375 , abstract =

    work page doi:10.1145/3490486.3538375 2022

  56. [56]

    Information Processing Letters , volume=

    Average performance of a greedy algorithm for the on-line minimum matching problem on Euclidean space , author=. Information Processing Letters , volume=. 1994 , publisher=

    1994

  57. [57]

    Bansal, Nikhil and Buchbinder, Niv and Gupta, Anupam and Naor, Joseph , booktitle=. An. 2007 , organization=

    2007

  58. [58]

    Algorithmica , volume=

    Online algorithms for maximum cardinality matching with edge arrivals , author=. Algorithmica , volume=. 2019 , publisher=

    2019

  59. [59]

    R. J. Serfling , journal =. Probability Inequalities for the Sum in Sampling without Replacement , urldate =

  60. [60]

    Journal of the American statistical association , volume=

    Probability inequalities for sums of bounded random variables , author=. Journal of the American statistical association , volume=. 1963 , publisher=

    1963

  61. [61]

    Random Walk and the Area below Its Path , urldate =

    Arie Harel , journal =. Random Walk and the Area below Its Path , urldate =

  62. [62]

    and Kemp, Adrienne W

    Johnson, Norman L. and Kemp, Adrienne W. and Kotz, Samuel , doi =. Hypergeometric Distributions , booktitle =. https://onlinelibrary.wiley.com/doi/pdf/10.1002/0471715816.ch6 , year =

    work page doi:10.1002/0471715816.ch6