1 Introduction↩︎

In recent years, there has been much interest in revisiting classical online problems through the lens of online problems with delay (e.g. [1]–[3]). In such problems, instead of serving every request immediately, one can choose to delay the service of a request while accumulating a delay cost, and the total cost of a solution is the cost of serving all requests plus the accumulated delay costs. In such problems, the trade-off between service cost and delay cost is at the center of the decision making of an online algorithm: the algorithm can wait until many requests have arrived and then apply an offline algorithm to serve them cheaply as a batch, but this will incur a large delay cost.

In this paper, we study the Min-Cost Perfect Matching with Delay (MPMD) problem proposed by Emek et al. [4]. In MPMD, there is an underlying metric space of \(n\) points in which \(m\) requests arrive over time at different points. At every moment when there is an available request, the online algorithm can choose to either match it with another request and incur a connection cost equal to the distance between the locations of two requests, or to leave it unmatched and incur a delay cost.

MPMD has many intuitive interpretations and real-life applications. For example, suppose that one needs to design a mechanism for an online game platform which always needs to match two players to compete against each other. The mechanism wants to match two players who have similar levels to each other as this could reduce their dissatisfaction, which is a connection cost that the platform wants to minimize. The platform is allowed to choose not to match a player immediately but to wait for another player whose level is close enough to the first player to join the game and then to match them, so that the connection cost can be reduced. However, if one player has been waiting too long, they might lose patience and become more and more unsatisfied with this game platform, which will incur more delay cost instead. Therefore, the online algorithm needs to balance the trade-off between these two types of costs, which is at the center of studies in this area. This kind of problems are inherently online since we do not know what will come in the future, and once we have made a decision, it is irreversible.

1.0.0.0.1 Delay costs.

While the connection cost of a match is the distance between the locations of the two requests that are matched, there are various delay models according to how the delay cost increases at every moment when there is at least one request pending. Some delay models apply a uniform delay function that the total delay of each request is a function of the time different between its arrival and being matched, e.g. linear [4], convex [5], and concave delays [6]. The most general framework is that the delay increment is a function of the set of requests that are pending at every moment and the algorithm is non-clairvoyant that it does not know future delay functions, e.g. set and size-based delays [7].

1.0.0.0.2 Competitive ratios: \(n\) vs \(m\).

Prior studies on these delay models have achieved results that express competitive ratios as functions of \(n\) or \(m\). Note that \(m\) can be incomparably larger than \(n\) when the request sequence is sufficiently long, and such algorithms can perform badly even on a simple one-point metric when \(m\) tends to infinity (e.g. [8]). Thus, we aim at designing algorithms whose competitive ratios depend only on \(n\).

1.1 Our Contributions↩︎

In this paper, we make contributions to the study of two generalizations of linear delay functions mentioned above that are much less understood than the others: size-based and convex delays.

1.1.0.0.1 Size-based delay (MPMD-Size).

In the size-based delay setting, at every step the delay increment is a monotone function of the number of currently pending requests (See 3.1 for a formal definition). We prove bounds on the deterministic and randomized competitive ratios in terms of \(n\). Previously, only upper bounds in terms of \(m\) are known.

We emphasize that the lower bounds in 1 2 are universal lower bounds: they apply to every metric space.

1 2 improve upon previous results on size-based delays by Deryckere and Umboh [7] in two ways. First, the previous upper bounds for both deterministic and randomized algorithms are expressed as functions of \(m\), the number of requests, while our results are expressed as functions of \(n\), the number of points in the given metric space, and thus is an improvement in the more interesting regime where \(m \gg n\). Second, we also provide a reduction from MTS to MPMD-Size while theirs is only from MPMD-Size to MTS, which exponentially improves lower bounds for both deterministic and randomized algorithms on every \(n\)-point metric. In contrast, their lower bound only holds for uniform metrics. Our results settle the deterministic competitive ratio, up to a constant. See 1 for a detailed comparison between our results and those by Deryckere and Umboh.

1.1.0.0.2 Convex delay (MPMD-Convex).

We also consider the convex delays on \(n\)-point uniform metrics, first studied by Liu et al. [5]. Convex delay is applicable to a lot of real-life scenarios as well, e.g., a gaming platform where players think it is acceptable to wait for a short period yet a longer delay can be more and more frustrating and even affect the player’s willingness to join the platform again. In this problem, there is a non-decreasing delay function \(f\) associated with every request and the delay cost of request \(r\) incurred until \(t\) is \(f(t-a(r))\), where \(a(r)\) is its arrival time, and the total delay cost is the sum of every request’s individual delay. The previous study by Liu et al. focused on the setting where \(f\) is non-decreasing, continuous, unbounded and satisfy \(f(0)=f'(0)=0\). They gave a deterministic lower bound of \(\Omega(n)\) and a matching upper bound when \(f\) is also a monomial.

We consider polynomials \(f\) such that \(f'(0)>0\). Prior to our work, the only known result is that when \(f\) is linear, the deterministic competitive ratio is \(O(1)\) [9]. Our second main result fills this gap and completes our understanding of the landscape of the competitive ratio of MPMD under uniform convex monotone polynomial delays on uniform metrics.

Surprisingly, for different delay functions, their local derivatives at \(t=0\) can totally change the competitiveness, even when they have the same superlinear asymptotic behavior when \(t\rightarrow\infty\). For example, the deterministic competitive ratio is \(\Omega(n)\) for \(f(t)=t^2\), yet a minor perturbation to \(f(t)=(t+\varepsilon)^2-\varepsilon^2\) by any small \(\varepsilon>0\) completely changes it to \(O(1)\). We will see in the proof that it is due to the approximability between \(f(t)\) and the linear delay \(g(t)=t\): as long as \(f(0)=f'(0)=0\), the ratio between \(f\) and \(g\) tends to \(0\) when \(t\) tends to \(0\) and so we cannot use \(g\) to approximate \(f\) within positive constant factors. The \(O(1)\)-competitive result applies to a broader class of functions beyond polynomials as well, even some exponential functions; see [morefunctions] for further discussion.

1.2 Our Techniques↩︎

1.2.0.0.1 MPMD-Size.

We employ a similar high-level approach as Deryckere and Umboh [7] of encoding MPMD-Size as a metrical task system (MTS) problem (defined in 2). Our key contribution is a significantly more efficient encoding.

The main idea is to define the MTS states so that matching requests in the MPMD-Size instance corresponds to a state transition in the MTS instance, and at each timestep, the instantaneous delay increment in the MPMD-Size instance can be realized by a cost vector in the MTS instance. Deryckere and Umboh used the obvious encoding in which there is an MTS state for each even-sized subset of the requests that have arrived so far, and the current MTS state is the set of requests that have been matched so far. While this makes it trivial to encode the instantaneous delay increment as an MTS cost vector—the cost of a state is exactly the instantaneous delay increment of the requests that have arrived but are not matched—the total number of MTS states is the number of all possible even-sized subsets of the requests, which is exponential in \(m\). It also complicates matters when applying MTS algorithms as the MTS state space grows as new requests arrive.

Our key insight that enables a more succinct encoding of MPMD-Size as MTS is the following. It never hurts to match two pending requests if they are co-located and so the number of unmatched requests at each point is either \(0\) or \(1\). Thus, to determine the number of unmatched requests (which in turn determines the instantaneous delay increment), it suffices to keep track for each point, whether there is an unmatched request at that point. This, in turn, can be done by keeping track of the parity of the number of times a request on that point has been previously matched (see the discussion following 1). Therefore, we can simply express the current state of an MPMD-Size algorithm using an \(n\)-dimensional Boolean vector. Thus, the total number of MTS states is \(O(2^n)\).

Finally, our reductions between MTS and MPMD-Size go in both directions. This lets us improve the lower bounds for both deterministic and randomized algorithms exponentially, and in particular, settle the deterministic competitive ratio (up to constants).

1.2.0.0.2 MPMD-Convex on uniform metrics.

Different from the linear delay, a convex delay function has an unbounded increase rate when it has been pending unmatched for enough long time. As a result, a reasonable algorithm should avoid this case, otherwise even a short period of waiting may lead to huge delay increase. Therefore, we introduce the concept of \(T\)-impatient algorithms, where a request that has been pending for time \(T\) must be matched immediately once there is another available request anywhere in the metric space. In this way, we naturally divide the time axis into two parts according to whether there is a request that has been pending for longer than time \(T\) at the moment. If there is no request that has been pending for longer than time \(T\), then the delay increase rate of every request is upper and lower bounded by two positive constants (to guarantee the positive lower bound, the property that \(f'(0)>0\) is necessary) and we can use the linear delay to approximate it up to a constant factor. As for the other case, based on the \(T\)-impatient property of the algorithm, the only reason that a request has been pending that long is because there is neither another pending request nor the arrival of a new request to be matched with, which means that there must be a request continuously pending throughout this time period under the optimal solution as well, which provides a lower bound of the optimal cost. Luckily, for all monotone polynomials, such a lower bound is within a constant factor of the delay incurred under the algorithm.

Therefore, to design an algorithm for monotone polynomial delays such that \(f'(0)>0\) on uniform metrics, it can be reduced to designing a \(T\)-impatient algorithm whose competitive ratio is a constant for linear delay on uniform metrics. We show that the seminal algorithm for MPMD on tree metrics by Azar et al. [9] does not satisfy the \(T\)-impatient property while being implemented on uniform metrics, and thus propose a new algorithm and prove it has the desired property.

1.3 Related Works↩︎

1.3.0.0.1 Linear delay.

When MPMD was first introduced by Emek et al. [4], the delay function they studied is the uniform linear delay. They proposed a randomized algorithm with competitive ratio \(O(\log^2 n+\log \Delta)\), where \(n\) is the number of points in the metric space and \(\Delta\) is its aspect ratio. Azar et al. [9] improved the upper bound of the randomized competitive ratio for linear delays to \(O(\log n)\) by designing an algorithm based on the randomized tree embedding technique into weighted HSTs from [10]. The current best lower bound for the uniform linear delay function is \(\Omega(\log n/\log\log n)\) of any randomized algorithm from [11], which shows a gap between known upper and lower bounds even for the most classical delay setting.

The above results that express competitive ratios in terms of \(n\) and \(\Delta\) usually require the algorithm to know the metric space beforehand, and such competitive ratios are independent of the length of the request sequence. However, there are also results where the competitive ratio is expressed in terms of \(m\), the number of requests in the input sequence, while the algorithm does not need to know the metric space prior to its execution: the first such result was proposed by Bienkowski et al. [12] and their deterministic algorithm is \(O(m^{2.46})\)-competitive. Bienkowski et al. [13] later improved the result to \(O(m)\) by an adaptation of the deterministic primal-dual moat growing technique, and independently and concurrently, Azar and Fanani [8] devised a sublinear \(O(m^{0.59})\)-competitive deterministic algorithm. So far, the best result that expresses the competitive ratio as a function of \(m\) is an \(O(\log^5 m)\)-competitive deterministic algorithm by Dufay and Wattenhofer [14].

1.3.0.0.2 Concave delay.

Azar et al. [6] considered the MPMD problem with uniform concave delays. They designed an \(O(1)\)-competitive deterministic algorithm for the single point and an \(O(\log n)\)-competitive randomized algorithm for general \(n\)-point metric spaces. Deryckere and Umboh [7] generalized the primal-dual framework from [13] and proposed an \(O(m)\)-competitive deterministic algorithm for uniform concave delays.

1.3.0.0.3 Convex delay.

Liu et al. [5] considered the MPMD problem with uniform convex delays on \(n\)-point uniform metric spaces. They studied monomial functions \(f(t)=t^{\alpha}\) such that \(\alpha>1\) (where \(t\) is the time difference between arrival and being matched for each request). They provided a deterministic \(O(n)\)-competitive algorithm and showed a matching deterministic lower bound of \(\Omega(n)\) for all uniform non-decreasing unbounded continuous delay functions such that \(f(0)=f'(0)=0\). This result demonstrates a gap between the solutions for the cases with linear and convex delays, as the algorithm proposed by Azar et al. [9] achieves constant competitive ratio on uniform metrics because uniform metrics can be seen as trees of height \(1\). They also provided a randomized \(\Omega(\log n)\) lower bound for delay functions in the same class. There is no result for convex delays beyond uniform metrics yet.

1.3.0.0.4 Set and size-based delays.

In all of the above studies, there is one uniform delay function \(f(t)\) known to the algorithm in advance that applies to every request from the input, suggesting how its delay cost increases as time goes by, and the total delay cost is the sum of delay costs incurred by each request. Deryckere and Umboh [7] studied another model of delay function that is not accumulated request-wise but step-wise: at every time step \(t\), the instantaneous delay cost is incurred as a function of the set of unmatched requests during this step. This set-delay model studies MPMD problem in the least restrictive way, as there is essentially no restriction on the structure of the delay functions and the setting is non-clairvoyant, i.e. the algorithm does not know future delays. Similar non-clairvoyant delay settings have been studied in other online problems with delays, e.g., TCP Acknowledgment Problem [15] and Subadditive Joint Replenishment Problem [16], [17]. Unfortunately, under the most general set-delay setting, every deterministic algorithm has competitive ratio of at least \(\Omega(\Delta)\), where \(\Delta\) is the aspect ratio of the metric space. Instead, Deryckere and Umboh further restricted to the case of size-based delays, which have natural applications in practical settings with service-level agreements such as cloud computing. They showed that there is an \(O(2^{m})\)-competitive deterministic algorithm and an \(O(m^{4})\)-competitive randomized algorithm by a reduction to the classical MTS problem introduced by Borodin et al. [18] and applying the best upper bounds for both deterministic and randomized algorithms by Borodin et al. and Bubeck et al. [19] respectively. They also provided lower bounds in terms of \(n\), which is \(\Omega(n)\) for deterministic algorithms and \(\Omega(\log n)\) for randomized algorithms. These upper and lower bounds show significant gaps between \(m\) and \(n\) in the scenarios where a request sequence of unbounded length is generated on a given finite metric.

1.3.0.0.5 Paper organization.

We start by introducing the formal definition of MTS in 2. In 3, we show the reductions between MPMD-Size and MTS on both directions and hence complete the proof of Theorems 1 and 2. We study MPMD-Convex on uniform metrics and prove 3 in 4. We conclude by some discussion on the results as well as open problems.

2 Preliminaries↩︎

In this section, we introduce the definition and properties of the Metrical Task System problem, which will be used in 3 to prove the main results of our paper on MPMD-Size. The formal definitions and notations of MPMD-Size and MPMD-Convex, two different delay models of MPMD that we study, are in Sections 3 and 4 respectively.

The metrical task system (MTS) problem, introduced by Borodin et al. [18], can be defined as a sequence of requests \(\{\rho_{t}\}_{t\geq 1}\) on a given finite metric space \((V,d)\) and an initial state \(s_{0}\in V\) of the server. Each request \(\rho_{t}: V\rightarrow \mathbb{R}_{\geq 0}\) is a non-negative cost function on the state space \(V\), illustrating the cost of the server to process request \(\rho_{t}\) in different points from \(V\). Upon the arrival of request \(\rho_{t}\) at every step \(t\geq 1\), the server can be moved to some state \(s_{t}\in V\) to process \(\rho_{t}\), and this incurs service cost of \(\rho_{t}(s_{t})\). Since MTS is an online problem, the state \(s_{t}\) at every step \(t\) must be output without knowing future requests. The total cost of a solution \(\{s_{t}\}_{t\geq 1}\) that expresses the state \(s_{t}\) where the server processes request \(\rho_{t}\) at every step \(t\geq 1\) consists of service cost and transition cost, where the transition cost at every step \(t\) is the distance \(d(s_{t-1},s_{t})\) of moving to \(s_{t}\) from its previous state \(s_{t-1}\). As a result, the cost of a solution \(\{s_{t}\}_{t\geq 1}\) is defined as: \[\sum_{t\geq 1}[\rho_{t}(s_{t})+d(s_{t-1},s_{t})].\]

For MTS problems, we say that an online algorithm \(\mathcal{A}\) is lazy if: at every step \(t\) when it moves from \(s_{t-1}\) to a different state \(s_{t}\) to process \(\rho_{t}\), it must hold that \(\rho_{t}(s_{t-1})>0\). Intuitively speaking, a lazy algorithm \(\mathcal{A}\) only makes a move when its current state incurs positive cost for the upcoming request while always staying still if the service cost of the new request in the current state is zero.

From now on, we can assume that every MTS algorithm that we use is lazy.

Let MTS-Single denote the subclass of MTS problem where every request \(\rho_{t}\) incurs positive cost at exactly one point \(v_{t}\in V\), i.e. \(\rho_{t}(v_{t})>0\) and \(\rho_{t}(v)=0\) for every \(v\in V\setminus \{v_{t}\}\). When a metric space is given, we use \(c_{\mathrm{m}}\) to denote the minimum possible worst-case competitive ratio that can be achieved by an algorithm for MTS problem on it, and \(c_{\mathrm{ms}}\) to denote that can be achieved for MTS-Single problem. The following result is folklore for both deterministic and randomized algorithms:

For completeness, we include the proofs of Lemmas [lazy] and [single] in the Appendix. They will be used in 3 to establish the reductions between MPMD-Size and MTS.

3 Reduction between MPMD-Size and MTS↩︎

In this section, we first formally define the MPMD problem with size-based delays (MPMD-Size), and then describe the reduction between it and MTS.

3.1 Definition and Property of MPMD-Size↩︎

The MPMD problem is defined on a metric space \((V,d)\), where \(V\) is the set of points and \(d:V\times V\rightarrow \mathbb{R}_{\geq 0}\) is the distance function. An online input consists of a sequence of requests that arrive over time. Every request \(r\) is defined by two characteristics: its arrival time \(a(r)\) and location \(\ell(r)\in V\). We view the problem in the discrete way that any request can only arrive at a time step \(t\in\mathbb{N}_{>0}\), yet it is possible that multiple requests arrive at the same time step \(t\). This model captures the original definition by Emek et al. [4] when we divide the continuous time axis into discrete steps where a step covers an interval of infinitesimal length.

Suppose \(Q_t\) is the set of requests that have arrived up to and including time step \(t\). At every step, the instantaneous delay function \(f_{t}:2^{Q_t}\rightarrow \mathbb{R}_{\geq 0}\) specifies the increment of delay cost at this step for every possible \(P_t\subseteq Q_t\), where \(P_{t}\) is the set of requests that are pending during time step \(t\). At every step \(t\), the algorithm first sees the newly-arriving requests (if any) and the instantaneous delay function \(f_{t}\), then makes a decision on matching some requests. A match between two requests \(r_{1}\) and \(r_{2}\) incurs a connection cost of \(d(\ell(r_{1}), \ell(r_{2}))\). This process results in an updated \(P_{t}\), and the instantaneous delay \(f_{t}(P_{t})\) is then incurred after the matching performed at step \(t\). Observe that the definition is consistent with metrical task systems (defined in 2) in the sense that at every step, the algorithm first sees the new input, then decides which state to move to (possibly the same state), and incurs the cost of the resulting state. The goal is to minimize the sum of its connection cost and delay cost incurred among all steps.

In the MPMD-Size problem, the instantaneous delay function incurred at time step \(t\) can be expressed as \(f_{t}(|P_{t}|)\), where \(f_{t}:\mathbb{N}_{\geq0}\rightarrow \mathbb{R}_{\geq0}\) is a monotone function. We note that the well-studied linear delay cost is a special case of the size-based delay where \(f_{t}(|P_{t}|)=|P_{t}|\) at every moment \(t\).

We say that an online algorithm \(\mathcal{A}\) is smart if no two requests are pending at the same point during any time step. One important property of sized-based delay functions is that we can without loss of generality assume that every algorithm or solution is smart, because of the following lemma:

1 provides us with not only a nice property of the optimal solution, but also a mechanism of online transformations that allows us to always automatically match two requests at the same point immediately at any moment. As a result, we do not need to explicitly describe the a match of two requests at the same point in the metric anymore. Based on this, we can assume that at every point \(v\in V\) there is either one or zero pending request at every time step \(t\), and there are at most \(n\) requests pending in the whole metric space \(V\). Moreover, at every given time step, we can refer to a match between two requests at two different points as a match between these two points without ambiguity. Throughout the paper, we may use expressions such as “the algorithm matches point \(v_{1}\) with point \(v_{2}\)” and “point \(v\) has been matched for an odd number of times”, where the former refers to a match between requests at these two points \(v_{1}\) and \(v_{2}\), and the latter refers to the total number of times where a request at \(v\) has been matched with some request at another point. As we have discussed in 1.2, this allows us to encode the state of an algorithm with a Boolean vector that has an entry over every point in \(V\), which builds the foundation of our reductions.

3.2 Construction of MTS Metric Space↩︎

Before we formally describe the reduction between two problems, we first specify the corresponding metric space \((\mathcal{K}^{V},D)\) on which the request sequence for both MTS and MTS-Single problems is based, given a metric space \((V,d)\) for an MPMD-Size instance.

Observe that \(|\mathcal{K}^{V}| = 2^{n-1}\).

3.2.0.0.1 Intuition for \((\mathcal{K}^{V},D)\).

To have an intuitive understanding of the structure of \((\mathcal{K}^{V},D)\) defined on a metric \((V,d)\) and its addition operation, we can give a Boolean variable to every point in \(V\), and see every match between two points in \(V\) as an operation that flips the Boolean variable associated with these two points simultaneously. If the default setting is that the Boolean variable associated with every point in \(V\) is \(0\), then \(\mathcal{K}^{V}\) is exactly the set of states that can be attained by applying the matching operations, where each state is a Boolean vector that specifies the value of the Boolean variable associated with every point in \(V\). With this intuition, if the cost of a match is exactly the distance of the two points involved in it, then the distance between two states in \(\mathcal{K}^{V}\) should be the minimum cost to transform one state into another by applying matching operations.

As a result, we define the concept of the induced matching of every element in \(\mathcal{K}^{V}\) (3) and use it to express the distance \(D\) on \(\mathcal{K}^{V}\). We will see that this definition of distance indeed satisfies the min-cost transformation property between every two states (5).

We use \(\mathbf{0}\) to denote \((0)_{v\in V}\) and \(\mathbf{1}\) to denote \((1)_{v\in V}\). We first note that \(\mathcal{K}^{V}\) is a closed subgroup of \(\{0,1\}^{V}\) under this addition operation.

We defer the proof of the following claim to the Appendix.

3.3 From MPMD-Size to MTS↩︎

Given any instance of MPMD-Size on the metric space \((V,d)\), we first describe the reduction from it to an instance of MTS on the corresponding \((\mathcal{K}^{V},D)\), as well as how to translate an online algorithm for MTS to one for the original MPMD-Size.

We introduce some notations to express the state of an MPMD-Size instance under the execution of a given algorithm at step \(t\), including: the total arrivals of requests at different points, and the effect of all matches made by the algorithm so far.

In MPMD-Size, at every step \(t\), new requests arrive and the instantaneous delay function \(f_{t}\) is revealed at the same time, and an online algorithm needs to make decisions to match according to this information. At each step \(t\), we need to handle two situations: when new requests have arrived at \(t\) and before the algorithm has made new decisions yet, and after the algorithm has made decisions at time \(t\). The former determines the matchings that the algorithm can make, and the latter determines the instantaneous cost incurred at the end of step \(t\). With notations introduced in 5, it is easy to see that the former state can be expressed as \(R_{t}\oplus M_{t-1}\) and the latter state can be expressed as \(R_{t}\oplus M_{t}\). With the smart algorithm property and the mechanism shown in 1, it is not hard to see that we can assume that requests at the same point cancel out each other automatically for state \(R_{t}\oplus M_{t-1}\) as well. We summarize the above discussion in the following observation that expresses the number of request at every point with a Boolean vector:

If \((M_{t-1}\oplus R_t)(v)=0\), then there is no request pending at \(v\) after new arrivals at \(t\), and of course there cannot be any request at \(v\) after new matches are performed at \(t\) as well, thus leading to the following observation:

For every \(\mathbf{u}\in \{0,1\}^{V}\), we use \(|\mathbf{u}|\) to denote the number of \(1\)’s among all entries of \(\mathbf{u}\), i.e. \(|\mathbf{u}|=\sum_{v\in V}\mathbf{u}(v)\). During every step \(t\) when the delay cost is incurred, \(R_{t}\oplus M_{t}\) is the Boolean vector that denotes the state of the input under the algorithm as per [matchandarrival]. Based on these notations and the property of size-based delays, the delay cost incurred during step \(t\) can be expressed as \(f_{t}(|R_{t}\oplus M_{t}|)\).

3.3.0.0.1 Construction of MTS instance.

Now we are ready to define the MTS instance that we reduce MPMD-Size to. We set the server’s initial position of the MTS instance to be \(C_{0}=\mathbf{0}\). Upon every time step \(t\geq 1\), we assign a request vector \((\rho_{t}({\mathbf{u}}))_{\mathbf{u}\in\mathcal{K}^{V}}\) to the MTS instance according to \(R_{t}\), the Boolean vector that we have defined to denote the parity of the number of requests that have arrived at each point in \(V\) until (and including) \(t\), and \(f_{t}\), the instantaneous delay cost function of the MPMD-Size instance incurred at step \(t\). More specifically, the cost to process \(\rho_{t}\) at \(\mathbf{u}\) is \(\rho_{t}({\mathbf{u}})=f_{t}(|R_{t}\oplus \mathbf{u}|)\) for every \(\mathbf{u}\in\mathcal{K}^{V}\).

Let \(\mathrm{OPT}_{\mathrm{m}}\) denote the value of the optimal solution of the MTS instance and \(\mathrm{OPT}_{\mathrm{size}}\) denote that of the MPMD-Size instance.

3.3.0.0.2 Translating MTS algorithm to MPMD-Size.

We now describe how to transform an algorithm \(\mathcal{A}_{\mathrm{m}}\) for the MTS instance to one \(\mathcal{A}_{\mathrm{size}}\) for the MPMD-Size instance in an online way. As we see from the proof of 2, there is naturally a one-to-one correspondence between the current MTS state and the current total matching Boolean vector \(M_t\) of MPMD-Size, which can be seen as the state of an MPMD-Size algorithm. Therefore, given an online algorithm \(\mathcal{A}_{\mathrm{m}}\) for MTS problem on \((\mathcal{K}^{V}, D)\) that processes request \(\rho_{t}\) at state \(C_{t}\), intuitively, we want to transit MPMD-Size algorithm to state \(M_{t}=C_t\) as well. However, such a transition is not always feasible, as there is no guarantee that there is an available request at every point that the algorithm needs to match to transit to \(C_{t}\). If this happens, then we want to update \(M_{t-1}\) to \(M_{t}\) that is the closest possible to \(C_{t}\) among all feasible matchings that can be made: we check every pair of match in the min-cost perfect matching induced by \(M_{t-1}\oplus C_{t}\), and match every feasible pair of requests. See the description of Algorithm 1 for more details.

The following claim guarantees the local optimality of \(\mathcal{A}_{\mathrm{m}}\) as per the transition from \(M_{t-1}\) to \(M_t\) by matches at step \(t\):

We prove that the cost of \(\mathcal{A}_{\mathrm{size}}\) is no more than that of \(\mathcal{A}_{\mathrm{m}}\) by the following lemmas. First, we compare the instantaneous delay cost of \(\mathcal{A}_{\mathrm{size}}\) incurred at step \(t\) with the cost of processing task \(\rho_{t}\) by \(\mathcal{A}_{\mathrm{m}}\), and this is where the size-based property of the delay function \(f_{t}\) plays a vital role.

The next lemma compares the connection cost of \(\mathcal{A}_{\mathrm{size}}\) (which is \(D(M_{t-1}, M_t)\) at every step \(t\) according to [local32optimality]) with the transition cost of \(\mathcal{A}_{\mathrm{m}}\).

Combining 3 4, we conclude that the total cost of \(\mathcal{A}_{\mathrm{size}}\) on the MPMD-Size instance on \((V,d)\) is no more than the total cost of \(\mathcal{A}_{\mathrm{m}}\) on the MTS instance on \((\mathcal{K}^{V},D)\), yielding the following theorem of the reduction.

Applying the upper bound of \(O(N)\) for deterministic algorithms from [18] and that of \(O(\log ^{2}N)\) for randomized algorithms from [19] of MTS on every \(N\)-point metric gives the upper bounds in Theorems 1 and 2.

3.4 From MTS-Single to MPMD-Size↩︎

In this part, we establish the reduction from any given instance of MTS-Single on \((\mathcal{K}^{V},D)\) to one of MPMD-Size on \((V,d)\), where \(V\) is a given metric space and \(|V|=n\).

3.4.0.0.1 MPMD-Size delay function.

We first state the structure of the size-based delay function \(f_{t}\) of the MPMD-Size instance for every step \(t\geq 1\): \[f_{t}(N) = \begin{cases} 0 & \text{if } N<n ;\\ \varepsilon_t & \text{if } N\geq n. \end{cases}\] Here \(\varepsilon_t\) denotes a positive amount in our construction that will depend on the request of the MTS-Single instance at step \(t\). More specifically, at every step \(t\) there is exactly one point that is “hit” with a positive cost by the request in MTS-Single, and we use \(\varepsilon_t\) to denote the amount of this positive cost.

3.4.0.0.2 Requests of MPMD-Size instance.

We assume that the initial setting of the MTS server is \(C_0=\mathbf{0}\), otherwise we set \(R_t\oplus\mathbf{u}_t=C_0\oplus \mathbf{1}\) and show that the property maintained in the proof of 6 is \(M_t\oplus C_t=C_0\) for every step \(t\) instead (it is intuitively like “shifting" both \(R_t\) and \(M_t\oplus C_t\) by \(C_0\)). At every step \(t\) when the new request \(\rho_{t}\) arrives in the MTS-Single instance on \((\mathcal{K}^{V},D)\), suppose that \(\rho_{t}(\mathbf{u}_{t})=\varepsilon_t>0\) and \(\rho_{t}(\mathbf{u})=0\) for every \(\mathbf{u}\in \mathcal{K}^{V}\setminus \{\mathbf{u}_{t}\}\), then we set \(R_t=\mathbf{u}_t\oplus \mathbf{1}\) for the MPMD-Size instance. To have a more intuitive understanding of how new requests arrive in the metric space at step \(t\), we use the difference between \(R_{t-1}\) and \(R_{t}\), i.e. \(R_{t-1}\oplus R_{t}\), to denote the new arrivals at step \(t\), such that \((R_{t-1}\oplus R_{t})(v)=1\) if and only if a new request arrives at step \(t\) at point \(v\), for every \(v\in V\). Moreover, we can express this amount as \(R_{t-1}\oplus R_{t}=R_{t-1}\oplus \mathbf{u}_t\oplus \mathbf{1}\), which can be computed from \(R_{t-1}\) that has been well-defined from previous steps, and \(\mathbf{u}_t\) defined by the new request of MTS-Single instance at step \(t\). As a result, the MPMD-Size instance that we reduce MTS-Single to is well-defined.

The following lemma provides a lower bound of a solution’s connection cost at step \(t\), given \(M_{t-1}\) and \(M_{t}\), the two consecutive states of matches that have been made so far.

Let \(\mathrm{OPT}_{\mathrm{ms}}\) denote the value of the optimal solution of the MTS-Single instance and \(\mathrm{OPT}_{\mathrm{size}}\) denote the that of the MPMD-Size instance.

The next step is to convert an online algorithm \(\mathcal{A}_{\mathrm{size}}\) for the MPMD-Size instance to one \(\mathcal{A}_{\mathrm{ms}}\) for the MTS-Single instance without increasing the cost. At every step \(t\) after new matches have been made by \(\mathcal{A}_{\mathrm{size}}\) and \(M_t\) is updated, \(\mathcal{A}_{\mathrm{ms}}\) processes request \(\rho_{t}\) in state \(M_{t}\).

Now the reduction from MTS-Single to MPMD-Size has been established as the following:

Combined with [single], we can use \(c_{\mathrm{m}}\), the competitive ratio of the general MTS problem, to provide lower bounds for the MPMD-Size problem. Therefore, we obtain the following corollary when we apply the universal lower bound of \(\Omega(N)\) for deterministic algorithms from [18] and that of \(\Omega(\log N)\) for randomized algorithms from [20] of MTS on every \(N\)-point metric.

This gives the lower bounds in Theorems 1 and 2.

4 MPMD-Convex on Uniform Metrics↩︎

In this section, we study another form of delay functions that does not fall in the category of size-based delays. We use the continuous time model to study the online matching with uniform delays, where the same monotone continuous delay function \(f:\mathbb{R}_{\geq 0}\rightarrow \mathbb{R}_{\geq 0}\) (we further assume that \(f(0)=0\) without loss of generality) applies to every request \(r\) in the following way: suppose the arrival time of a request \(r\) is \(a(r)\) and \(t\) is the time when it is matched by the algorithm, then the total delay cost incurred by request \(r\) is \(f(t-a(r))\). In this section, we still use \(\ell(r)\) to denote the location of request \(r\) in the metric space, and the connection cost of matching two requests \(r_{1}\) and \(r_{2}\) at locations \(\ell(r_{1})\) and \(\ell(r_{2})\) respectively is still \(d(\ell(r_{1}), \ell(r_{2}))\). The total cost of a solution consists of its total connection cost of matching request into pairs, and the sum of delay cost incurred by every request.

We study monotone convex polynomial delay functions \(f\) such that \(f'(0)>0\) on \(n\)-point uniform metrics where the distance between any two different points is \(2\delta>0\). Equivalently, such a metric can be interpreted as a star metric where leaf nodes are points in the metric space, the distance between every leaf and the root is \(\delta\), and the distance between two leaves is the length of the shortest path between them, which is \(2\delta\). The previous study by Liu et al. [5] gives a tight \(\Theta(n)\) deterministic bound for a class of convex delay functions (including all monotone polynomials) such that \(f(0)=f'(0)=0\), and our study complements the landscape by the following result for functions that \(f'(0)>0\):

The contrast of this result compared with the \(\Omega(n)\) deterministic lower bound of the case of continuous non-decreasing unbounded delays satisfying that \(f(0)=f'(0)=0\) demonstrates that even the local property of the delay function at time \(t=0\) significantly affects the solution and competitiveness of the online MPMD problem. Different from the linear delay case, here the distance \(2\delta\) between different points in the metric space also affects the competitive ratio: our algorithm is constant competitive under a fixed function \(f\) when \(\delta\) is considered as a constant (the same as the study by Liu et al. [5]), while the competitive ratio can also be regarded as a function of \(\delta\), which provides another parameter that might be interesting to study for convex delays.

4.1 Simpler Polynomials↩︎

Without loss of generality, we study \(f\) in the form \(f(t)=\frac{1}{k}t^{k}+t\) for \(k\geq 2\). To see why we can make this assumption, suppose that we have another polynomial \(h(t)=\sum_{i=1}^{k}a_{i}t^i\) that is monotone on \(\mathbb{R}_{\geq 0}\), such that \(a_{k}> 0, a_{1}>0\). ³ The following claim proves that \(h\) can be approximated by \(f\) within constant factors.

As a result, if there is a competitive algorithm for delay function \(f\), then the same algorithm can be applied to delay function \(h\) and the lost factor of the competitive ratio is within a constant factor that only depends on \(A\) and \(B\), independent of both \(n\) and \(\delta\).

If we apply this idea of comparing the costs of the same solution under different delay functions to comparing the convex delay function \(f(t)=\frac{1}{k}t^{k}+t\) with the classical linear delay function \(g(t)=t\) on the same request sequence, the only difference that can lead to different costs and different optimal solutions are delay functions \(f\) and \(g\). In the following part, we focus on the linear delay function \(g\), and prove that a competitive algorithm for \(g\) with certain properties also works well for \(f\). Given an algorithm \(\mathcal{A}\) and some delay function \(h\), we use \(\mathrm{cost}_{\mathcal{A}}(h)\) to denote the cost of \(\mathcal{A}\) when the delay function is set to \(h\). As the total cost consists of connection cost and delay cost, we use \(\mathrm{cost}^{d}_{\mathcal{A}}(h)\) to denote its connection cost and \(\mathrm{cost}^{t}_{\mathcal{A}}(h)\) to denote its delay cost. Similarly for any solution \(\mathrm{SOL}\), we use \(\mathrm{SOL}(h)\) to denote its total cost under \(h\), as well as \(\mathrm{SOL}^d(h)\) and \(\mathrm{SOL}^t(h)\) to denote its connection and delay costs respectively. These are the notations that we will use in computations in the next section.

4.2 \(T\)-Impatient Algorithms↩︎

For an online algorithm \(\mathcal{A}\) and a request \(r\), define \(t_{\mathcal{A}}(r)\) to be the time that \(r\) is matched by \(\mathcal{A}\).

Intuitively, a \(T\)-impatient algorithm will only leave a request \(r\) unmatched for more than \(T\) time only if there is no other request it can match \(r\) to. Equivalently, if a request \(r\) has been pending for time \(T\), then \(\mathcal{A}\) is going to match \(r\) with another request immediately as long as there is such a request available. The \(T\)-impatient property guarantees a lower bound of the optimal solution during the period when there is a request pending for longer than \(T\). On the other hand, when no request is pending for longer than \(T\), the delay increment can be approximated by the linear delay up to a constant factor as long as \(f'(0)>0\). These two properties guarantee the competitiveness of a \(T\)-impatient algorithm under convex delays.

The next lemma is the key to guaranteeing that the cost of a \(T\)-impatient algorithm during the period when there is a request that has been pending beyond time \(T\) is within a constant factor of the cost incurred by the optimal solution during the same period.

We now formally state the reduction from convex delay \(f(t)=\frac{1}{k}t^k+t\) to linear delay \(g(t)=t\) under any \(T\)-impatient algorithm.

With this reduction, now the goal is to find an \(T\)-impatient algorithm for some constant \(T\) independent of \(n\) that achieves competitive ratio \(\gamma\) under delay function \(g(t)=t\), where \(\gamma\) is a constant independent of \(n\) as well.

4.3 Constructing a \(T\)-Impatient Algorithm↩︎

In this section, we propose a \(T\)-impatient algorithm and prove that it is competitive under linear delay \(g(t)=t\), and thus a competitive algorithm under \(f(t)=\frac{1}{k}t^k+t\) according to 9.

4.3.0.0.1 High-level description.

Recall that a uniform metric can be regarded as a star where each leaf corresponds to a point in the metric space, and the distance between each leaf and the root is \(\delta\). We assign a counter to every vertex of the star graph, i.e. all leaves and the root.

During the execution of our algorithm (2), each request can be in one of three states: \(\mathsf{LEAF}\), \(\mathsf{ROOT}\) and \(\mathsf{READY}\). A request \(r\) is in \(\mathsf{LEAF}\) if and only if it is contributing to the increase of the leaf counter \(z_{\ell(r)}\) (\(\ell(r)\) is the location of \(r\)), in \(\mathsf{ROOT}\) if it is neither in \(\mathsf{LEAF}\) nor in \(\mathsf{READY}\). If we want to view the dynamic of a request moving between states, then after a request \(r\) arrives, initially it is in \(\mathsf{LEAF}\) until \(z_{\ell(r)}\) is saturated (if \(z_{\ell(r)}\) is already saturated at arrival time \(a(r)\), we can still say that the time length when \(r\) is in \(\mathsf{LEAF}\) is zero). Once \(z_{\ell(r)}\) is saturated, \(r\) transits to \(\mathsf{ROOT}\), and will only transit from \(\mathsf{ROOT}\) to \(\mathsf{READY}\) if the condition of either Case 1 or Case 2 is satisfied. The state transition diagram \(\mathsf{LEAF}\rightarrow\mathsf{ROOT}\rightarrow \mathsf{READY}\) is acyclic, which means that once a request \(r\) transits to the next state, there is no way back to the previous state. Based on the fact that the counter \(z_{\ell(r)}\) is saturated is equivalent to that \(r\) is in \(\mathsf{ROOT}\) or \(\mathsf{READY}\) for a pending request \(r\), the conditions to trigger a match between two requests at different points can also be expressed as: either both are in \(\mathsf{ROOT}\), or one is in \(\mathsf{READY}\).

Note that the priority rule guarantees that if one request is in \(\mathsf{READY}\), then it should be matched immediately as long as there is another pending request, which is vital in guaranteeing the \(T\)-impatient property.

4.3.0.0.2 Overview of analysis.

Our analysis is similar to that in [9], [11] in the sense that we analyze counters associated with different points separately, where the time axis can be divided into phases for each counter according to when it is saturated, and we compare the algorithm with another given solution based on alignment status (to be defined later). The biggest difference is that their algorithms only match two requests on a uniform metric when both counters associated with these two requests are saturated, while our algorithm has another case that a request in \(\mathsf{READY}\) is matched with another request immediately when it appears without waiting for another request’s counter to also be saturated. This is the key property that makes 2 satisfy the desired \(T\)-impatient property. To deal with this case for the cost analysis, we prove that the total cost incurred by matches of this case provides a lower bound of the optimal cost as well, hence proving that our new algorithm is also competitive.

Throughout the analysis, we use \(\mathrm{ALG}\) to denote both the algorithm that we propose and its cost, and \(\mathrm{SOL}\) to denote a fixed offline solution and its cost that we are comparing \(\mathrm{ALG}\) with, and the costs are always incurred under delay function \(g\). The superscripts \(d\) and \(t\) that represent connection and delay costs respectively work in the same way as before.

We first note that our algorithm is smart (defined in 3.1) as well, which will be used for the alignment status analysis that we are going to introduce.

We can also assume that [smart-con] holds for every offline solution \(\mathrm{SOL}\), because linear delay is a special case of the size-based delay and 1 holds for this case as well. Our delay function is continuous, which means that the instantaneous delay increment at the discrete moments when a match occurs is negligible. As a result, if we want to compare the status of pending requests under \(\mathrm{ALG}\) with another solution \(\mathrm{SOL}\), at every moment there are four cases at every point \(v\in V\): there is one request pending at \(v\) under both \(\mathrm{ALG}\) and \(\mathrm{SOL}\), there is no request pending at \(v\) under both \(\mathrm{ALG}\) and \(\mathrm{SOL}\), there is one request pending at \(v\) under \(\mathrm{ALG}\) but no request pending at \(v\) under \(\mathrm{SOL}\), there is one request pending at \(v\) under \(\mathrm{SOL}\) but no request pending at \(v\) under \(\mathrm{ALG}\). We say that a point \(v\in V\) is aligned if it is one of the first two cases among the four, otherwise \(v\) is misaligned.

We say that a request \(r\) carries \(v\) if \(\mathrm{ALG}\) makes a match between \(r\) that is in \(\mathsf{READY}\) and a request at \(v\neq\ell(r)\). For such a request \(r\), let \(t_{1}(r)\) be the moment when it starts to be in \(\mathsf{ROOT}\) and \(t_{2}(r)\) be the moment when it starts to be in \(\mathsf{READY}\).

The following corollary is a direct result of combining [nonoverlapping] and 10.

Now we start to analyze the cost of \(\mathrm{ALG}\) under the linear delay \(g(t)=t\) based on the increments of all leaf counters \(z_{v}\)’s and \(z_{u}\). For each leaf counter \(z_{v}\), let \(y_{v}\) denote the total increments of the value of \(z_{v}\) throughout the execution of \(\mathrm{ALG}\) without any reset. Similarly, let \(y_{u}\) denote the final value of the root counter \(z_{u}\) since the value of \(z_{u}\) is never reset to zero.

Now we need to relate the final value \(y_{u}\) of the root counter and \(y_{v}\)’s of leaf counters to the cost of any \(\mathrm{SOL}\). Given a solution \(\mathrm{SOL}\), for every leaf \(v\), let \(x_{v}\) denote the delay cost incurred by requests at \(v\), \(x'_{v}\) denote the connection cost incurred by matching \(v\) with another point (i.e. \(x'_v=k\delta\) if \(v\) is matched with another point for \(k\) times by \(\mathrm{SOL}\), and the total connection cost is just the sum among all leaf points). We introduce an additional term based on \(\mathrm{ALG}\) rather than \(\mathrm{SOL}\), which is \(b_{v}\), to denote the number of times that \(v\) is carried by another request under the execution of \(\mathrm{ALG}\).

5 Discussions and Open Problems↩︎

In this paper, we improved both upper and lower bounds of MPMD-Size on every \(n\)-point metric space. We show that the problem is equivalent to MTS on another \(2^{n-1}\)-point metric space, and the results are consistent with the state-of-the-art results of MTS. The deterministic competitive ratio is settled up to a constant as the \(\Theta(N)\) bound of MTS holds for every \(N\)-point metric. However, there is still a gap between the upper and lower bounds for randomized algorithms. This is because the randomized competitive ratio of MTS depends on metric structures: as the randomized competitive ratio of \(O(\log N)\) can be achieved on some \(N\)-point metrics like uniform metrics [18] and weighted stars [19], there also exist \(N\)-point metrics where the lower bound of \(\Omega(\log ^{2}N)\) holds [20]. As a result, to make further improvements, we need to study the structure of the metric space \((\mathcal{K}^{V}, D)\). Given a metric space \((V,d)\), the definition of \((\mathcal{K}^{V}, D)\) is naturally from the Boolean status of every point in \(v\), with some similarities to the earthmover distance, yet this structure has not been well studied, and may be of independent interest.

Our study of MPMD-Convex on uniform metrics covers the case \(f'(0)>0\) that has not been considered before, and very surprisingly, such local property at \(t=0\) totally changes the competitiveness compared with the case \(f'(0)=0\). As the majority of smooth convex delay functions have been covered on uniform metrics, the natural open problem is to design an algorithm for convex delays on more general metrics. There are still some open problems on uniform metrics as well: when we consider randomization, there is only a lower bound of \(\Omega(\log n)\) for unbounded, non-decreasing and continuous functions that \(f(0)=f'(0)=0\), while it is open whether there is a randomized algorithm that can achieve competitive ratio of \(O(\log n)\) in this case. As for the case \(f'(0)>0\), we note that although 2 achieves constant competitive ratio when the distance between points is a fixed constant \(2\delta\), the competitive ratio depends on \(\delta\) and tends to infinity when \(\delta\) is sufficiently large. This is different from the linear delay case where the scale of the metric does not affect the competitive ratio. As a result, it might be interesting to study whether it is possible to design an algorithm whose competitive ratio is also independent of \(\delta\).

Another natural research direction is to study the bipartite case of MPMD-Size and MPMD-Convex, where every request has either positive or negative polarity and only requests of opposite polarities can be matched. The online min-cost bipartite perfect matching with delay problem has been studied for linear [11] and concave delays [6], yet there is no result for convex or size-based delay. While the proofs and results by Deryckere and Umboh [7] can be easily adapted for the bipartite matching problem by treating every even-sized subset whose sum of polarities is zero as an MTS state, our method for MPMD-Size does not easily extend to the bipartite case as it is not sufficient to express the states with Boolean vectors because multiple requests of the same polarity can accumulate at the same location.

References↩︎

---

1. A perfect matching exists since \(|T_{\mathbf{u}}|\) is even, by the definition of \(\mathcal{K}^{V}\).↩︎

2. \(T_1\sqcup T_2\) is the disjoint union of \(T_1\) and \(T_2\).↩︎

3. We need \(a_1> 0\) to have \(h'(0)>0\).↩︎