  We consider the online Minimum-Cost Perfect Matching with Delays (MPMD)
problem introduced by Emek et al. (STOC 2016), in which a general metric space
is given, and requests are submitted in different times in this space by an
adversary. The goal is to match requests, while minimizing the sum of distances
between matched pairs in addition to the time intervals passed from the moment
each request appeared until it is matched.
  In the online Minimum-Cost Bipartite Perfect Matching with Delays (MBPMD)
problem introduced by Ashlagi et al. (APPROX/RANDOM 2017), each request is also
associated with one of two classes, and requests can only be matched with
requests of the other class.
  Previous algorithms for the problems mentioned above, include randomized
$O\left(\log n\right)$-competitive algorithms for known and finite metric
spaces, $n$ being the size of the metric space, and a deterministic
$O\left(m\right)$-competitive algorithm, $m$ being the number of requests.
  We introduce
$O\left(m^{\log\left(\frac{3}{2}+\epsilon\right)}\right)$-competitive
deterministic algorithms for both problems and for any fixed $\epsilon > 0$. In
particular, for a small enough $\epsilon$ the competitive ratio becomes
$O\left(m^{0.59}\right)$. These are the first deterministic algorithms for the
mentioned online matching problems, achieving a sub-linear competitive ratio.
Our algorithms do not need to know the metric space in advance.
