Greedy Metric Minimum Online Matchings with Random Arrivals



Gairing, Martin and Klimm, Max
(2019) Greedy Metric Minimum Online Matchings with Random Arrivals. Operations Research Letters, 47 (2). pp. 88-91.

[img] Text
parking-orl-revision.pdf - Author Accepted Manuscript

Download (274kB)

Abstract

We consider online metric minimum bipartite matching problems with random arrival order and show that the greedy algorithm assigning each request to the nearest unmatched server is n-competitive, where n is the number of requests. This result is complemented by a lower bound exhibiting that the greedy algorithm has a competitive ratio of at least n (ln3−ln2)∕ln4 ≈n 0.292 , even when the underlying metric space is the real line.

Item Type: Article
Uncontrolled Keywords: Random arrival, Matching, Greedy algorithm, Approximation
Depositing User: Symplectic Admin
Date Deposited: 08 Jan 2019 10:48
Last Modified: 19 Jan 2023 01:07
DOI: 10.1016/j.orl.2019.01.002
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3030948