  In this paper, we study $k$-Way Min-cost Perfect Matching with Delays - the
$k$-MPMD problem. This problem considers a metric space with $n$ nodes.
Requests arrive at these nodes in an online fashion. The task is to match these
requests into sets of exactly $k$, such that the space and time cost of all
matched requests are minimized. The notion of the space cost requires a
definition of an underlying metric space that gives distances of subsets of $k$
elements. For $k>2$, the task of finding a suitable metric space is at the core
of our problem: We show that for some known generalizations to $k=3$ points,
such as the $2$-metric and the $D$-metric, there exists no competitive
randomized algorithm for the $3$-MPMD problem. The $G$-metrics are defined for
3 points and allows for a competitive algorithm for the $3$-MPMD problem. For
$k>3$ points, there exist two generalizations of the $G$-metrics known as $n$-
and $K$-metrics. We show that neither the $n$-metrics nor the $K$-metrics can
be used for the $k$-MPMD problem. On the positive side, we introduce the
$H$-metrics, the first metrics to allow for a solution of the $k$-MPMD problem
for all $k$. In order to devise an online algorithm for the $k$-MPMD problem on
the $H$-metrics, we embed the $H$-metric into trees with an $O(\log n)$
distortion. Based on this embedding result, we extend the algorithm proposed by
Azar et al. (2017) and achieve a competitive ratio of $O(\log n)$ for the
$k$-MPMD problem.
