  We consider the online minimum cost matching problem on the line, in which
there are $n$ servers and, at each of $n$ time steps, a request arrives and
must be irrevocably matched to a server that has not yet been matched to, with
the goal of minimizing the sum of the distances between the matched pairs.
Despite achieving a worst-case competitive ratio that is exponential in $n$,
the simple greedy algorithm, which matches each request to its nearest
available free server, performs very well in practice. A major question is thus
to explain greedy's strong empirical performance. In this paper, we aim to
understand the performance of greedy over instances that are at least partially
random. When both the requests and the servers are drawn uniformly and
independently from $[0,1]$, we show that greedy is constant competitive, which
improves over the previously best-known $O(\sqrt{n})$ bound. We extend this
constant competitive ratio to a setting with a linear excess of servers, which
improves over the previously best-known $O(\log^3{n})$ bound. We moreover show
that in the semi-random model where the requests are still drawn uniformly and
independently but where the servers are chosen adversarially, greedy achieves
an $O(\log{n})$ competitive ratio. When the requests arrive in a random order
but are chosen adversarially, it was previously known that greedy is
$O(n)$-competitive. Even though this one-sided randomness allows a large
improvement in greedy's competitive ratio compared to the model where requests
are adversarial and arrive in a random order, we show that it is not sufficient
to obtain a constant competitive ratio by giving a tight $\Omega(\log{n})$
lower bound. These results invite further investigation about how much
randomness is necessary and sufficient to obtain strong theoretical guarantees
for the greedy algorithm for online minimum cost matching, on the line and
beyond.

Data Structures and Algorithms