Online minimum matching with uniform metric and random arrivals

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

doi:10.1016/j.orl.2021.12.005

Online minimum matching with uniform metric and random arrivals

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

Computer Science

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

We consider Online Minimum Bipartite Matching under the uniform metric. We show that Randomized Greedy achieves a competitive ratio equal to (1+1/n)(H_n+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 language	English (US)
Pages (from-to)	45-49
Number of pages	5
Journal	Operations Research Letters
Volume	50
Issue number	1
DOIs	https://doi.org/10.1016/j.orl.2021.12.005
State	Published - Jan 2022

All Science Journal Classification (ASJC) codes

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

Keywords

Online minimum matching
Random arrival order
Uniform metric space

Access to Document

10.1016/j.orl.2021.12.005

Cite this

@article{9fea85e131a640659f666f4565f24d72,

title = "Online minimum matching with uniform metric and random arrivals",

abstract = "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.",

keywords = "Online minimum matching, Random arrival order, Uniform metric space",

author = "Duppala, {Sharmila V.S.} and Sankararaman, {Karthik A.} and Pan Xu",

note = "Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",

year = "2022",

month = jan,

doi = "10.1016/j.orl.2021.12.005",

language = "English (US)",

volume = "50",

pages = "45--49",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - Online minimum matching with uniform metric and random arrivals

AU - Duppala, Sharmila V.S.

AU - Sankararaman, Karthik A.

AU - Xu, Pan

PY - 2022/1

Y1 - 2022/1

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

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

KW - Online minimum matching

KW - Random arrival order

KW - Uniform metric space

UR - http://www.scopus.com/inward/record.url?scp=85121249774&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85121249774&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2021.12.005

DO - 10.1016/j.orl.2021.12.005

M3 - Article

AN - SCOPUS:85121249774

SN - 0167-6377

VL - 50

SP - 45

EP - 49

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -

Online minimum matching with uniform metric and random arrivals

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this