Greedy Metric Minimum Online Matchings with Random Arrivals

Gairing, Martin ORCID: 0000-0002-0569-7113 and Klimm, Max (2019) Greedy Metric Minimum Online Matchings with Random Arrivals. Operations Research Letters, 47 (2). pp. 88-91. ISSN 0167-6377, 1872-7468

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:	06 Jun 2025 13:45
DOI:	10.1016/j.orl.2019.01.002
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3030948