Online minimum matching with uniform metric and random arrivals

Sharmila V.S. Duppala, Karthik A. Sankararaman, Pan Xu

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


We consider Online Minimum Bipartite Matching under the uniform metric. We show that Randomized Greedy achieves a competitive ratio equal to (1+1/n)(Hn+1−1), which matches the lower bound. Comparing with the fact that RG achieves an optimal ratio of Θ(ln⁡n) for the same problem but under the adversarial order, we find that the weaker arrival assumption of random order doesn't offer any extra algorithmic advantage for RG, or make the model strictly more tractable.

Original languageEnglish (US)
Pages (from-to)45-49
Number of pages5
JournalOperations Research Letters
Issue number1
StatePublished - Jan 2022

All Science Journal Classification (ASJC) codes

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics


  • Online minimum matching
  • Random arrival order
  • Uniform metric space


Dive into the research topics of 'Online minimum matching with uniform metric and random arrivals'. Together they form a unique fingerprint.

Cite this