Keywords

1 Introduction

Consider an online gaming platform supporting two-player games such as Chess. In such a platform, players arrive one-by-one over time, and stay in a queue to participate in a match. The platform then tries to suggest a suitable opponent for each player from the queue. In order to satisfy the players, the platform aims to maximize the quality of the matched games. Specifically, we aim to minimize the distance of the matched players (e.g., the difference of their ratings) as well as the sum of the players’ waiting time.

The above situation can be modeled as the problem called Online Matching with Delays, introduced by Emek et al. [11]. In the setting, arriving requests (or players) are embedded in a metric space so that the distance of each pair is determined. For the Online Matching with Delays, Emek et al. [11] proposed a randomized algorithm with a competitive ratio of \(O(\log ^2 n + \log \varDelta )\), where n is the number of points in a metric space, and \(\varDelta \) is the ratio of the maximum to minimum distance between two points. The competitive ratio was later improved to \(O(\log n)\) by Azar et al. [5]. We remark that both algorithms require that a metric space is finite and all the points in the metric space are known in advance (we note that arriving requests may be embedded into the same point more than once). Bienkowski et al. [9] presented a primal-dual algorithm with a competitive ratio of O(m), where m is the number of requests. Another algorithm with a better competitive ratio of \(O(m^{0.59})\) was proposed by Azar et al. [6].

In this paper, we consider a generalization of Online Matching with Delays, called the Min-cost Perfect k-way Matching with Delays (k-MPMD) [22]. In the problem, requests arrive one-by-one over time. At any time, instead of choosing a pair of requests, we make a group of k requests. This corresponds to an online gaming platform that allows more than two players to participate, such as mahjong (\(k = 4\)), Splatoon (\(k = 8\)), Apex Legends (\(k = 60\)), and Fortnite (\(k = 100\)). Then we aim to partition all the requests into groups of size-k subsets, minimizing the sum of the distance of the requests in the same group and the total waiting time.

To generalize to k-MPMD, it is necessary to measure the distance of a group of \(k>2\) requests. That is, we need to introduce a metric space that defines distances for any subset of k points. Although there are many ways of generalizing a standard distance between two points to \(k>2\) points in the literature [4, 16], Melnyk et al. [22] showed that most known generalized metrics on k points cannot achieve a bounded competitive ratio for the k-MPMD. Melnyk et al. [22] then introduced a new interesting class of generalized metric, called H-metric, and proposed a randomized algorithm for the k-MPMD on H-metric with a competitive ratio of \(O(k^{5}\log n)\), extending Azar et al. [5].

The main contribution of this paper is to propose a deterministic algorithm for the k-MPMD on H-metric with a competitive ratio of \(O(mk^2)\), where m is the number of requests. The proposed algorithm adopts a primal-dual algorithm based on a linear programming relaxation of the k-MPMD.

To design a primal-dual algorithm, we first formulate a linear programming relaxation of the offline problem, that is, when a sequence of requests is given in advance. We remark that even the offline setting is NP-hard when \(k\ge 3\), as it includes the triangle packing problem. We first show that H-metric can be approximated by a standard metric (Theorem 1). This allows us to construct a linear programming problem with variables for each pair of requests such that the optimal value gives a lower bound on the offline version of the k-MPMD. Using the linear programming problem, we can design a primal-dual algorithm by extending the one by Bienkowski et al. [9] for Online Matching with Delays. We show that, by the observation on H-metric (Theorem 1) again, the cost of the output can be upper-bounded by the dual objective value of our linear programming problem.

An interesting special case of the H-metric is the diameter on a line. That is, points are given on a 1-dimensional line, and the distance of k points is defined to be the maximum difference in the k points. In the context of an online gaming platform, the diameter on a line can be interpreted as the difference of players’ ratings. In this case, we show that the competitive ratio of our algorithm can be improved to \(O(m + k^2)\). Moreover, we construct an instance such that our algorithm achieves the competitive ratio of \(\varOmega (m/k)\).

Related Work. An online algorithm for the matching problem was first introduced by Karp et al. [15]. They considered the online bipartite matching problem where arriving requests are required to match upon their arrival. Since then, the problem has been studied extensively in theory and practice. For example, motivated by internet advertising, Mehta et al. [20] generalized the problem to the AdWords problem. See also Mehta [21] and Goel and Mehta [13]. The weighted variant of the online bipartite matching problem is considered in the literature. It includes the vertex-weighted online bipartite matching [1], the problem with metric costs [8, 23, 25], and the problem with line metric cost [2, 12, 14, 17]. We remark that the edge-weighted online bipartite matching in general has no online algorithm with bounded competitive ratio [1].

This paper deals with a variant of the online matching problem with delays, in which arriving requests are allowed to make decision later with waiting costs. Besides the related work [5, 6, 9, 11] mentioned before, Liu et al. [18] extended the problem to the one with non-linear waiting costs. Other delay costs are studied in [7, 10, 19]. Ashlagi et al. [3] studied the online matching problem with deadlines, where each arriving request has to make a decision by her deadline. Pavone et al. [24] considered online hypergraph matching with deadlines.

Paper Organization. This paper is organized as follows. In Sect. 2, we formally define the minimum-cost perfect k-way matching problem and H-metric. We also discuss useful properties of H-metrics which will be used in our analysis. In Sect. 3, we present our main algorithm for the k-MPMD on H-metric. In Sect. 4, we show that there exists an instance such that our algorithm admits an almost tight competitive ratio. Due to the space limitation, the proofs of lemmas and theorems are omitted, which may be found in the full version of this paper.

2 Preliminaries

2.1 Minimum-Cost Perfect k-Way Matching with Delays

In this section, we formally define the problem k-MPMD. Let \((\chi , d)\) be a generalized metric space where \(\chi \) is a set and \(d: \chi ^k \rightarrow [0, \infty )\) represents a distance among k elements.

In the problem, m requests \(u_1, u_2, \ldots , u_m\) arrive one-by-one in this order. The arrival time of \(u_i\) is denoted by \(\textrm{atime}(u_i)\). When \(u_i\) arrives, the location \(\textrm{pos}(u_i)\) of \(u_i\) in the metric space \(\chi \) is revealed. Thus, an instance of the problem is given as a tuple \(\sigma =(V, \textrm{atime}, \textrm{pos})\), where \(V=\{u_1, \dots , u_m\}\), \(\textrm{atime}: V\rightarrow \mathbb {R}_+\), and \(\textrm{pos}: V\rightarrow \chi \) such that \(\textrm{atime}(u_1)\le \dots \le \textrm{atime}(u_m)\). We note that m may be unknown in advance, but we assume that m is a multiple of k.

At any time \(\tau \), with the only information for requests arrived so far, an online algorithm can make a set of k requests \(v_1, \ldots , v_k\) in V, where we say that \(v_1, \ldots , v_k\) are matched, if they satisfy the following two conditions: (a) The requests \(v_1, \ldots , v_k\) have already arrived, that is, \(\textrm{atime}(v_i) \le \tau \) for any \(i=1,\dots , k\); (b) None of \(v_1, \ldots , v_k\) has been matched to other requests yet. The cost to match \(v_1, \ldots , v_k\) at time \(\tau \) is defined to be

$$ d(\textrm{pos}(v_1), \textrm{pos}(v_2), \ldots , \textrm{pos}(v_k)) + \sum _{i=1}^k (\tau - \textrm{atime}(v_i)). $$

The first term means the distance cost among the k requests and the second term is the total waiting cost of the k requests.

The objective of the problem is to design an online algorithm that matches all the requests, minimizing the total cost. In other words, an online algorithm finds a family of disjoint subsets of size k that covers all the requests. We call a family of disjoint subsets of size k a k-way matching, and a k-way matching is called perfect if it covers all the requests.

To measure the performance of an online algorithm, we define the competitive ratio. For an instance \(\sigma \), let \(\mathcal {ALG}(\sigma )\) be the cost incurred by the online algorithm, and let \(\mathcal {OPT}(\sigma )\) be the optimal cost when we know in advance a sequence of requests V as well as \(\textrm{atime}(u_i)\) and \(\textrm{pos}(u_i)\) for each request \(u_i\). The competitive ratio of the online algorithm is defined as \(\sup _{\sigma } \frac{\mathcal {ALG(\sigma )}}{\mathcal {OPT(\sigma )}}\).

2.2 H-Metric

In this section, we define H-metric, introduced by Melnyk et al. [22]. Recall that a function \(d:\chi ^2\rightarrow [0, \infty )\) is called a distance function (or a metric) if d satisfies the following three axioms:

  • (Symmetry) \(d(p_1, p_2) = d(p_2, p_1)\) for any \(p_1, p_2\in \chi \).

  • (Positive definiteness) \(d(p_1, p_2) \ge 0\) for any \(p_1, p_2\in \chi \), and \(d(p_1, p_2) = 0\) if and only if \(p_1 = p_2\).

  • (Triangle inequality) \(d(p_1, p_3) \le d(p_1, p_2) + d(p_2, p_3)\) for any \(p_1, p_2, p_3\in \chi \).

We first define a k-point metric as a k-variable function satisfying generalizations of the symmetry axiom and the positive definiteness axiom.

Definition 1

We call a function \(d: \chi ^k \rightarrow [0, \infty )\) a k-point metric if it satisfies the following two axioms.

  • \(\varPi \): For any permutation \(\pi \) of \(\{p_1, \ldots , p_k\}\), we have \(d(p_1, \ldots , p_k) = d(\pi (p_1), \ldots , \pi (p_k))\).

  • \(O_D\): It holds that \(d(p_1, \ldots , p_k) \ge 0\). Moreover, \(d(p_1, \ldots , p_k) = 0\) if and only if \(p_1 = p_2 = \cdots = p_k\).

There are several ways of generalizing the triangle inequality to k-variable functions. One possibility is the following axiom: for any \(p_1, \ldots , p_k, a \in \chi \) and any \(i \in \{1, \dots , k\}\), it holds that

$$ {\varDelta _H:\ }d(p_1, \ldots , p_k) \le d(p_1, \ldots , p_i, \underbrace{a, \ldots , a}_{k - i}) + d(\underbrace{a, \ldots , a}_{i}, p_{i + 1}, \ldots , p_k). $$

We note that it is identical to the triangle inequality when \(k=2\).

For a multiset S on \(\chi \), we denote by elem(S) the set of all distinct elements contained in S. In addition to the generalized triangle inequality, we consider the relationship between \(d(p_1, \ldots , p_k)\) and \(d(p'_1, \ldots , p'_k)\) when \(elem(\{p_1, \ldots , p_k\}) \subseteq elem(\{p'_1, \ldots , p'_k\})\). The separation axiom \(\mathcal {S}_H\) says that, for some nonnegative integer \(\gamma \le k-1\),

$$\begin{aligned} d(p_1, \ldots , p_k) &\le d(p'_1, \ldots , p'_k) \quad \text {if}\,\, elem(\{p_1, \ldots , p_k\}) \subset elem(\{p'_1, \ldots , p'_k\}),\\ d(p_1, \ldots , p_k) &\le \gamma \cdot d(p'_1, \ldots , p'_k)\quad \text {if}\,\, elem(\{p_1, \ldots , p_k\}) = elem(\{p'_1, \ldots , p'_k\}). \end{aligned}$$

The H-metric is a k-point metric that satisfies all the above axioms.

Definition 2

(Melnyk et al. [22]). A k-point metric \(d_H: \chi ^k \rightarrow [0, \infty )\) is an H-metric with parameter \(\gamma \le k-1\) if it satisfies \(\varPi \), \(O_D\), \(\varDelta _H\) and \(\mathcal {S}_H\) with parameter \(\gamma \).

We remark that there are weaker conditions than \(\varDelta _H\) and \(\mathcal {S}_H\), generalizing the triangle inequality, which yields other classes of k-point metrics such as the n-metric [4] and the K-metric [16]. See [22] for the formal definition. Melnyk et al. [22], however, showed that the k-MPMD cannot be solved for such more general metrics. Specifically, they proved that there exists no randomized algorithm for the k-MPMD \((k \ge 5)\) problem on n-metric or K-metric agaist an oblivious adversary that has a competitive ratio which is bounded by a function of the number of points n.

2.3 Properties of H-Metric

In this section, we discuss approximating H-metric by a standard metric, and present specific examples of H-metric.

Melnyk et al. proved that H-metric can be approximated by the sum of distances between all pairs [22, Theorem 6]. We refine their results as in the theorem below, which will be used in the next section.

Theorem 1

Let \(d_H\) be an H-metric on \(\chi \) with parameter \(\gamma \). Define a metric \(d: \chi ^2 \rightarrow [0, \infty )\) as

$$ d(p_1, p_2) := d_H(p_1, p_2, \ldots , p_2) + d_H(p_2, p_1, \ldots p_1) $$

for any \(p_1, p_2\in \chi \). Then it holds that

$$\begin{aligned} \frac{1}{\gamma k^2} \cdot \sum _{i = 1}^{k - 1}\sum _{j=i+1}^{k} d(p_i, p_j) \le d_H(p_1, \ldots , p_k) \le \sum _{i=1}^k d(v, p_i), \end{aligned}$$
(1)

for all \(v \in \{p_1, \ldots , p_k\}\).

We conclude this section with providing specific examples of H-metric. We note that the examples below satisfy that \(\gamma =1\), and thus the approximation factor in Theorem 1 becomes small.

Let \(d:\chi ^2\rightarrow [0, \infty )\) be a distance function. We define a k-point metric \(d_{\max }\) by \(d_{\max } (p_1, \dots , p_k)=\max _{i,j\in \{1,\dots , k\}}d(p_i, p_j)\). Then it turns out to be an H-metric.

Proposition 1

Let \(d:\chi ^2\rightarrow [0, \infty )\) be a distance function. Then the k-point metric \(d_{\max }\) is an H-metric with \(\gamma =1\).

For real numbers \(p_1, \dots , p_k\in \mathbb {R}\), we define the diameter on a line as \(d_{\textrm{D}}(p_1, \ldots , p_k) = \max _{i, j \in \{1,\dots , k\}} |p_i-p_j|\). By Proposition 1, \(d_{\textrm{D}}\) is an H-metric.

For a distance function \(d: \chi ^2 \rightarrow [0, \infty )\), we define another H-metric \(d_{\textrm{HC}}\) by

$$ d_{\textrm{HC}} (p_1, \dots , p_k) = \min \left\{ \sum _{e \in C} d(e) \mid C \subseteq \left( {\begin{array}{c}\chi \\ 2\end{array}}\right) , C \text { forms a Hamiltonian circuit in } \{ p_1, \dots , p_k \} \right\} $$

where \(\left( {\begin{array}{c}\chi \\ 2\end{array}}\right) =\{(p, q)\mid p, q\in \chi , p\ne q\}\). This means that \(d_{\textrm{HC}} (p_1, \dots , p_k)\) equals to the minimum cost of a Hamiltonian circuit contained in \(\{p_1, \dots , p_k\}\) with respect to cost d.

Proposition 2

Let \(d: \chi ^2 \rightarrow [0, \infty )\) be a distance function. Then the k-point metric \(d_{\textrm{HC}}\) is an H-metric with parameter \(\gamma =1\).

3 k-MPMD on H-Metric Space

This section proposes a primal-dual algorithm for k-MPMD on H-metric space. Let \((\chi , d_H)\) be an H-metric space with parameter \(\gamma \).

3.1 Linear Programming Relaxation

This subsection introduces a linear programming relaxation for computing the offline optimal value \(\mathcal {OPT}(\sigma )\) for a given instance \(\sigma \).

We first give some notation. Let \(\mathcal {E}=\{F\subseteq V\mid |F|=k\}\). For any subset \(S \subseteq V\), we denote \(\textrm{sur}(S) = |S| \bmod k\), which is the number of remaining requests when we make a k-way matching of size \(\lfloor |S|/k\rfloor \) among S. We denote \(\varDelta (S)=\{F\in \mathcal {E}\mid F\cap S \ne \emptyset , F\setminus S\ne \emptyset \}\), which is the family of k request sets that intersect both S and \(V\setminus S\).

Preparing a variable \(x_F\) for any subset \(F\in \mathcal {E}\), we define a linear programming problem:

figure a

where, for any \(F=(v_1, \dots , v_k)\in \mathcal {E}\), we define

$$ \mathrm {opt\text {-}cost}(F) := d_H(\textrm{pos}(v_1), \ldots , \textrm{pos}(v_k)) + \sum _{i = 1}^{k} \left( \max _{j} \textrm{atime}(v_j) - \textrm{atime}(v_i) \right) . $$

Notice that \(\mathrm {opt\text {-}cost}(F)\) is the cost of choosing F at the moment when all the requests in F have arrived.

Let \(\mathcal {M}\) be a perfect k-way matching with optimal cost \(\mathcal {OPT}(\sigma )\). Define a 0-1 vector \((x_F)_{F\in \mathcal {E}}\) such that \(x_F=1\) if and only if \(F\in \mathcal {M}\). Then the vector satisfies the constraint (2). Moreover, the cost incurred by \(F\in \mathcal {M}\) is equal to \(\mathrm {opt\text {-}cost}(F)\). This is because the optimal algorithm that returns \(\mathcal {M}\) chooses F at the moment when all the requests in F have arrived. Thus the objective value for the vector \((x_F)_{F\in \mathcal {E}}\) is equal to \(\mathcal {OPT}(\sigma )\), and hence the optimal value of \((\mathcal {P})\) gives a lower bound of \(\mathcal {OPT}(\sigma )\).

We further relax the above LP \((\mathcal {P})\) by replacing \(x_F\)’s with variables for all pairs of requests. Let \(E=\{(u, v)\mid u, v\in V, u\ne v\}\), and we prepare a variable \(x_e\) for any \(e\in E\). We often call an element in E an edge.

We denote by \(\delta (S)\) the set of pairs between S and \(V\setminus S\). Define the following linear programming problem:

figure b

where, for any \(e=(v_1, v_2)\in E\) with \(p_1 = \textrm{pos}(v_1)\) and \(p_2 = \textrm{pos}(v_2)\), we define

$$\begin{aligned} d(p_1, p_2) &:= d_H(p_1, p_2, \ldots , p_2) + d_H(p_2, p_1, \ldots , p_1),\text { and }\\ \mathrm {opt\text {-}cost}(e) &:= d(p_1, p_2) + |\textrm{atime}(v_1) - \textrm{atime}(v_2)|. \end{aligned}$$

The following lemma follows from Theorem 1.

Lemma 1

It holds that, for any \(F = (v_1, \ldots , v_k)\in \mathcal {E}\),

$$\begin{aligned} \frac{1}{\gamma k^2} \cdot \sum _{i = 1}^{k - 1} \sum _{j = i + 1}^{k} \mathrm {opt\text {-}cost}(v_i, v_j) \le \mathrm {opt\text {-}cost}(F) \le \sum _{i=1}^{k} \mathrm {opt\text {-}cost}(v, v_i), \end{aligned}$$
(4)

where \(v = \mathop \mathrm{arg~max}\limits _{u \in F} \textrm{atime}(u)\).

For any perfect k-way matching \(\mathcal {M}\), define an edge subset M such that \(e\in M\) if and only if the pair e is contained in some set F of \(\mathcal {M}\). Thus we represent each set in \(\mathcal {M}\) with a complete graph of k vertices. We will show below that the characteristic vector for M is feasible to \((\mathcal {P}')\). Here, for a subset \(X\subseteq E\), the characteristic vector \(\mathbbm {1}_X\in \{0,1\}^E\) is defined to be

$$\begin{aligned} \mathbbm {1}_X(x) = {\left\{ \begin{array}{ll} 1 &{} (x \in X) \\ 0 &{} (x \notin X) \end{array}\right. }. \end{aligned}$$

Moreover, this implies that the optimal value of (\(\mathcal {P'}\)), denoted by \(\mathcal {P'}(\sigma )\), is a lower bound of \(\mathcal {OPT}(\sigma )\) for any instance \(\sigma \).

Lemma 2

Let \(\mathcal {M}\) be a perfect k-way matching. Define an edge subset \(M = \{ (u, v) \in E \mid \exists F\in \mathcal {M}~\mathrm {s.t.}~u, v \in F \}\). Then \(x=\mathbbm {1}_M\) is a feasible solution to \(\mathcal {P'}\). Furthermore, \(\mathcal {P'}(\sigma ) \le \mathcal {OPT}(\sigma )\) holds.

The dual linear programming problem of \((\mathcal {P'})\) is

figure c

The weak duality of LP implies that \(\mathcal {D}'(\sigma ) \le \mathcal {P}'(\sigma )\), where \(\mathcal {D}'(\sigma )\) is the dual optimal value.

3.2 Greedy Dual for k-MPMD (GD-k)

We present our proposed algorithm, called Greedy Dual for k-MPMD(GD-k). The proposed algorithm extends the one by Bienkowski et al. [9] for 2-MPMD using the LP \((\mathcal {P}')\).

In the algorithm GD-k, we maintain a family of subsets of requests, called active sets. At any time, any request v arrived so far belongs to exactly one active set, denoted by A(v). We also maintain a k-way matching \(\mathcal {M}\). A request not in \(\bigcup _{F\in \mathcal {M}}F\) is called free, and, for a subset \(S\subseteq V\) of requests, \(\textrm{free}(S)\) is the set of free requests in S.

When request v arrives, we initialize \(A(v) = \{v\}\) and \(y_S=0\) for any subset \(S\subseteq V\) such that \(v\in S\). At any time, for an active set S such that \(\textrm{free}(S)\) is nonempty, we increase \(y_S\) with rate r, where r is set to be \(1/(\gamma k^2)\). Then, at some point, there exists an edge \(e=(u, v)\in E\) such that \(\sum _{S : e \in \delta (S)}y_S = \frac{1}{\gamma k^2} \cdot \mathrm {opt\text {-}cost}(e)\), which we call a tight edge. When it happens, we merge the active sets A(u) and A(v) to a large subset \(S=A(u)\cup A(v)\), that is, we update \(A(w)=S\) for all \(w\in S\). We also mark the tight edge e. If \(|\textrm{free}(S)| \ge k\), we partition \(\textrm{free}(S)\) arbitrarily into subsets of size k with \(\textrm{sur}(S)\) free requests, and add these size-k subsets to \(\mathcal {M}\).

The pseudo-code of the algorithm is given as in Algorithm 1.

Let T be the time when all requests are matched in the algorithm. For any subset S, we denote the value of \(y_S\) at time \(\tau \) in the algorithm by \(y_S(\tau )\).

Algorithm 1
figure d

Greedy Dual for k-MPMD

Full size image

We show that \(y_S\)’s maintained in Algorithm 1 are always dual feasible.

Lemma 3

For any request v, it holds that

$$\begin{aligned} \sum _{S: v \in S} y_S(\tau ) \le r \cdot (\tau - \textrm{atime}(v)) \end{aligned}$$
(6)

at any time \(\tau \ge \textrm{atime}(v)\). This holds with equality while v is not matched.

Lemma 4

Let \(r = \frac{1}{\gamma k^2}\). Then, at any time \(\tau \), \(y_S(\tau )\) maintained in Algorithm 1 is a feasible solution to \((\mathcal {D'})\).

3.3 Competitive Ratio of GD-k

To bound the competitive ratio of GD-k, we evaluate the distance cost and the waiting cost separately. We will show that each cost is upper-bounded by the dual optimal value of \(\mathcal {D'}(\sigma )\).

Waiting Cost. We can upper-bound the waiting cost of the output as follows.

Lemma 5

Let \(\mathcal {M}=\{M_1, \dots , M_p\}\) be a perfect k-way matching returned by Algorithm 1, and let \(\tau _\ell \) be the time when we match \(M_\ell \). Then it holds that

$$ \sum _{\ell =1}^{p}\sum _{i=1}^k (\tau _\ell - \textrm{atime}(v_{\ell , i})) = \frac{1}{r} \cdot \sum _{S \subseteq V} \textrm{sur}(S) \cdot y_S(T) \le \frac{1}{r} \cdot \mathcal {D'}(\sigma ), $$

where we denote \(M_\ell = \{v_{\ell ,1}, \dots , v_{\ell , k}\}\).

Distance Cost. We say that a set \(S\subseteq V\) is formerly-active at time \(\tau \) if S is not active at time \(\tau \), but has been active before time \(\tau \).

Lemma 6

Let S be an active or formerly-active set at time \(\tau \). Then, marked edges both of whose endpoints are contained in S form a spanning tree in S.

We now evaluate the distance cost.

Lemma 7

Let \(\mathcal {M}=\{M_1, \dots , M_p\}\) be a perfect k-way matching returned by Algorithm 1. Then it holds that

$$ \sum _{\ell =1}^{p} d(\textrm{pos}(v_{\ell ,1}), \dots , \textrm{pos}(v_{\ell , k})) \le 4\gamma mk\cdot \sum _S \textrm{sur}(S) \cdot (k - \textrm{sur}(S)) \cdot y_S(T) \le 4\gamma mk\mathcal {D'}(\sigma ), $$

where we denote \(M_\ell = \{v_{\ell ,1}, \dots , v_{\ell , k}\}\).

Competitive Ratio. Summarizing the above discussion, we obtain Theorem 2.

Theorem 2

Let \(d_H\) be an H-metric with parameter \(\gamma \). Setting \(r=1/(\gamma k^2)\), Greedy Dual for k-MPMD achieves a competitive ratio \((4mk + k^2)\gamma \) for k-MPMD.

Proof

Let \(\sigma \) be an instance of k-MPMD. It follows from Lemmas 5 and 7 that the cost of the returned perfect k-way matching is upper-bounded by \((4mk + k^2)\gamma \cdot \mathcal {D'}(\sigma )\). By the weak duality and Lemma 4, we observe that \(\mathcal {D'}(\sigma )\le \mathcal {P'}(\sigma ) \le \mathcal {OPT}(\sigma )\). Thus the theorem holds.    \(\square \)

Finally, we consider applying our algorithm to the problem with specific H-metrics such as \(d_{\max }\) and \(d_{\textrm{HC}}\) given in Sect. 2.3. Since they have parameter \(\gamma =1\), it follows from Theorem 2 that GD-k achieves a competitive ratio \(O(mk + k^2)\). In the case of \(d_{\max }\), we can further improve the competitive ratio.

Theorem 3

For the k-MPMD on a metric space \((\chi , d_{\max })\), GD-k achieves a competitive ratio \(O(m + k^2)\).

4 Lower Bound of GD-k for a Diameter on a Line

In this section, we show a lower bound on the competitive ratio for GD-k for the metric \(d_{\textrm{D}}\). Recall that \(d_{\textrm{D}}(p_1,\dots , p_k)=\max _{i, j\in \{1,\dots , k\}}|p_i-p_j|\) for \(p_1,\dots , p_k\in \mathbb {R}\).

We define an instance \(\sigma _l =(V, \textrm{pos}, \textrm{atime})\) where \(V=\{u_1, u_2, \dots , u_m\}\) as follows. Suppose that the number m of requests is equal to \(m = sk^2\) for some integer s. Let \(p_1, \dots , p_k\) be k points in \(\mathbb {R}\) such that \(d(p_i, p_{i+1}) = 2\) for any \(i=1, 2, \dots , k-1\).

For \(i=1, 2, \dots , sk\) and \(j=1,2,\dots , k\), define \(\textrm{atime}(u_{k(i-1)+j}) = t_i\) and \(\textrm{pos}(u_{k(i-1)+j}) =p_j\) for \(j=1, 2, \dots , k\), where we define \(t_1=0\) and \(t_i=1 + (2 i - 3)\varepsilon \) for \(i\ge 2\). Thus, at any time \(t_i\) (\(i=1, \dots , sk\)), the k requests \(u_{k(i-1)+1}, \dots , u_{k(i-1)+k}\) arrive at every point in \(p_1, \dots , p_k\), respectively.

Then it holds that \(\mathcal {OPT}(\sigma _l)\le k+k\varepsilon + k^3\varepsilon + mk\varepsilon \), while the output of GD-k has cost at least \(m + k + (m - k) \varepsilon \).

Theorem 4

For a metric space \((\mathbb {R}, d_{\textrm{D}})\), there exists an instance \(\sigma _l\) of m requests such that GD-k admits a competitive ratio \(\varOmega (\frac{m}{k})\).