Gairing, Martin and Klimm, Max
(2019)
Greedy Metric Minimum Online Matchings with Random Arrivals.
Operations Research Letters, 47 (2).
pp. 88-91.
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 |