  This paper studies a new online problem, referred to as \emph{min-cost
perfect matching with delays (MPMD)}, defined over a finite metric space (i.e.,
a complete graph with positive edge weights obeying the triangle inequality)
$\mathcal{M}$ that is known to the algorithm in advance. Requests arrive in a
continuous time online fashion at the points of $\mathcal{M}$ and should be
served by matching them to each other. The algorithm is allowed to delay its
request matching commitments, but this does not come for free: the total cost
of the algorithm is the sum of metric distances between matched requests
\emph{plus} the sum of times each request waited since it arrived until it was
matched. A randomized online MPMD algorithm is presented whose competitive
ratio is $O (\log^{2} n + \log \Delta)$, where $n$ is the number of points in
$\mathcal{M}$ and $\Delta$ is its aspect ratio. The analysis is based on a
machinery developed in the context of a new stochastic process that can be
viewed as two interleaved Poisson processes; surprisingly, this new process
captures precisely the behavior of our algorithm. A related problem in which
the algorithm is allowed to clear any unmatched request at a fixed penalty is
also addressed. It is suggested that the MPMD problem is merely the tip of the
iceberg for a general framework of online problems with delayed service that
captures many more natural problems.
