# Online matching with delays and stochastic arrival times

Mathieu Mari, Michał Pawłowski, Runtian Ren, Piotr Sankowski University of
Warsaw and IDEAS NCBR, Warsaw, Poland<EMAIL_ADDRESS>of
Warsaw and IDEAS NCBR, Warsaw, Poland<EMAIL_ADDRESS>of Warsaw and IDEAS NCBR, Warsaw, Poland<EMAIL_ADDRESS>of
Warsaw and IDEAS NCBR, Warsaw, Poland<EMAIL_ADDRESS>
###### Abstract

This paper presents a new research direction for the Min-cost Perfect Matching
with Delays (MPMD) — a problem introduced by Emek et al. (STOC’16). In the
original version of this problem, we are given an $n$-point metric space,
where requests arrive in an online fashion. Our goal is to minimise the
matching cost for an even number of requests. However, contrary to traditional
online matching problems, a request does not have to be paired immediately at
the time of its arrival. Instead, the decision of whether to match a request
can be postponed for time $t$ at a delay cost of $t$. For this reason, the
goal of the MPMD is not only to minimise the distance cost of the generated
matching but to minimise the overall sum of distance and delay costs.
Interestingly, it is proved that in the standard case of the adversarially
generated requests, no online algorithm can achieve a competitive ratio better
than $O(\log n/\log\log n)$ (Ashlagi et al., APPROX/RANDOM’17).

Here, we consider a stochastic version of the MPMD problem where the input
requests follow a Poisson arrival process. For such problem, we show that the
above lower bound can be improved by presenting two deterministic online
algorithms which, in expectation, are constant competitive, i.e., the ratio
between the expected costs of the output matching and the optimal offline
solution is bounded by a constant. The first one is a simple greedy algorithm
that matches any two requests once the sum of their delay costs exceeds their
connection cost, i.e., the distance between them. The second algorithm builds
on the tools used to analyse the first one in order to obtain even better
performance guarantees. This result is rather surprising as the greedy
approach for the adversarial model achieves a much worse competitive ratio of
$\Omega(m^{\log\frac{3}{2}+\varepsilon})$, where $m$ denotes the number of
requests served (Azar et al., TOCS’20). Finally, we prove that it is possible
to obtain similar results for the general case when the delay cost follows an
arbitrary positive and non-decreasing function, as well as for the MPMD
variant with penalties to clear pending requests.

##  1 Introduction

Imagine players logging into an online platform to compete against each other
in a two player game. The platform needs to pair them in a way that maximises
the overall satisfaction from the gameplay. Typically, a player prefers to be
matched with someone with similar gaming skills. Thus, the platform has to
consider the experience gap when pairing two players. This skill level
difference is referred to as the _connection cost_. Additionally, once logged
in, a player can tolerate some waiting time to be matched — this is why the
platform can postpone the pairing decision in the hope of a better matching to
be found (i.e., the login of another player with similar skills). Nonetheless,
the waiting time for each player has its limits. A player may become
unsatisfied if their gaming request has been ignored for too long. This time
gap between logging into the platform and joining a gaming session is referred
to as the _delay cost_. The platform’s goal is to pair all the online players
into sessions, such that the total connection cost plus the total delay cost
produced is minimised.

The above is an example of an online problem called Min-cost Perfect Matching
with Delays (MPMD) [18]. It has drawn researchers attention recently [18, 2,
1, 13, 12, 24, 6, 7] due to many real-life applications ranging from Uber
rides, dating platforms, kidney exchange programs etc. In all of these
scenarios we can delay a matching decision at respective cost. This is in
contrary to the classical online matching [23], where decisions need to be
taken immediately.

Formally, the problem of MPMD is defined as follows. The input is a set of $m$
requests arriving at arbitrary times in a metric space
$\mathcal{M}=(\mathcal{X},d)$ equipped with a distance function $d$. Here, $m$
is an even integer, and $\mathcal{X}$ denotes the set of points in
$\mathcal{M}$. Each request $r$ is characterised by its _location_
$\ell(r)\in\mathcal{X}$ and _arrival time_ $t(r)\in\mathbb{R}^{+}$. When two
requests $r$ and $r^{\prime}$ are matched into a pair at time
$t\geq\max\\{t(r),t(r^{\prime})\\}$, a _connection cost_
$d(\ell(r_{1}),\ell(r_{2}))$ plus a _delay cost_ $(t-t(r_{1}))+(t-t(r_{2}))$
is incurred for producing such a pair. The target is to minimise the total
cost produced by the online algorithm for matching all the requests into
pairs.

Previously, the MPMD problem was studied in an adversarial model where an
online adversary generated the requests at different times in the given metric
space $\mathcal{M}$. Under this adversarial model, no online algorithm can
achieve a constant competitive ratio:

  * -

if the metric is known in advance, the current best competitiveness is $O(\log
n)$ (here $n$ denotes the number of points in the metric) [2] and no online
algorithm can achieve competitive ratio better than $\Omega(\log n/\log\log
n)$ [1];

  * -

if the metric is not known in advance, the current best competitiveness is
$O(m^{\log\frac{3}{2}+\varepsilon})$ (with $\varepsilon>0$ arbitrarily small),
achieved tightly by a deterministic online greedy algorithm [6].

It is often too pessimistic to assume no stochastic information on the input
is available — again, consider the example of matching gaming requests. The
online gaming platform has all the historical data and can estimate the
arrival frequency of the players with each particular skill level on an hourly
basis. Therefore, it is reasonable to assume that the gaming requests follow
some stochastic distribution. Furthermore, since thousands of requests
(representing players from all over the world) arrive every second, we can
assume that the requests are mutually independent. Based on these
observations, the following question can be naturally stated: in the case when
stochastic information on the input is available, can we devise online
algorithms for MPMD with better performance guarantees?

In this paper, we provide an affirmative answer to the question above. We
consider a stochastic online version of MPMD, by assuming that the requests
arrive following a Poisson arrival process. To be more precise, the waiting
time between any two consecutive requests arriving at any metrical point $x$,
follows an exponential distribution ${\rm Exp}(\lambda_{x})$ with parameter
$\lambda_{x}$. Under such a model, the goal of the platform is to minimise the
expected cost produced by an algorithm ${\rm ALG}$ to deal with a random input
sequence consisting of $m$ requests. To evaluate the performance of our
algorithms on stochastic inputs, we use the ratio-of-expectations, that
corresponds to the ratio of the expected cost of the algorithm to the expected
cost of the optimal offline solution (see Definition 4).

The Poisson arrival model might seem non-intuitive at first sight. However, we
know that this is a convenient generalisation of the uniform distribution
model to an online setting, i.e., when we do not know the number of requests
to arrive. This follows by the fact that for uniform parameters $\lambda_{x}$
and conditioned on the exact number of points $m$, this model is equivalent to
the process when each point chooses uniformly and independently at random the
time to arrive [27].

#### Our Contribution.

We prove that the performance guarantee obtained in the Poisson arrival model
is significantly better compared with the current best competitiveness
obtained in the adversarial model. More specifically, we show that an
intuitive _Greedy_ algorithm, which matches any two requests immediately when
their total delay cost reaches their distance, achieves a constant ratio-of-
expectations.

######  Theorem 1.

For MPMD in the Poisson arrival model, the Greedy algorithm achieves a ratio-
of-expectations of $16/(1-e^{-2})$.

To prove this theorem, we apply the following strategy. We first notice that
the connection cost of a Greedy solution is at most its delay cost. Thus, it
becomes the core of the proof to upper bound the delay cost. For this purpose,
in Section 3, we define the _radius_ $\rho_{x}\geq 0$ for each metric point
$x$. Such a radius depends on the parameters of the problem and roughly
corresponds to the expected delay time for matching the requests located on
$x$. Then, we show how to use the radius to lower bound the cost of the
optimal offline solution. Intuitively, we prove that a request located on $x$
is in expectation responsible for a total cost of $\Omega(\rho_{x})$. At this
point, it is worth emphasising once again that in the adversarial model when
the metric is not known in advance the best known competitive ratio is
$\Omega(m^{\log\frac{3}{2}+\varepsilon})$) (see the counter example in [6],
Appendix A).

This notion of radius suggests another potential algorithm for MPMD with
stochastic inputs. Indeed, when a new request $r$ arrives on a point $x$, we
know that this request will wait for a time $O(\rho_{x})$ in average before
being matched by the Greedy algorithm. In particular, $r$ will be matched with
another request that is at distance $O(\rho_{x})$. Therefore, if at the time
of the $r$’s arrival, there is another pending111By pending we mean that at
that time, the request is still unmatched by the algorithm. request
$r^{\prime}$ that is at distance less than $\rho_{x}$, why not match these two
requests directly? In Section 3, we formalise this intuition and design an
algorithm called _Radius_. Thanks to these anticipated pairings, the
performance ratio is improved by a factor of 2.

######  Theorem 2.

For MPMD in the Poisson arrival model, the Radius algorithm achieves a ratio-
of-expectations of $8/(1-e^{-2})$.

Finally, we show how to adjust the Greedy and the Radius algorithms to deal
with other variants of the MPMD problem in a way that preserves constant
performance ratio. In Section 7, we look at the generalisation of the problem
where a request can be delayed for a time $t$ at a cost $f(t)$, where $f$ is a
given positive and non-decreasing function. We show that, unless $f$ is such
that the expected cost of the optimal offline solution is infinite, our
algorithms achieve constant performance ratios, where the constants only
depend on the delay cost function $f$. In Section 8, we consider the variant
of MPMD where we are allowed to clear pending requests for a fixed penalty
cost.

#### Related work.

The MPMD problem was introduced by Emek et al. [18]. In their paper, they
proposed a randomised online algorithm that achieves a competitive ratio of
$O(\log^{2}n+\log\Delta)$, where $n$ is the number of points of the metric
space and $\Delta$ is the aspect ratio. Later, Azar et al. [2] improved the
competitive ratio to $O(\log n)$, thereby removing the dependence of $\Delta$
in the competitive ratio. Both of these papers randomly embed the metric space
into a tree of distortion $O(\log n)$, and then propose online algorithms on
tree metrics. In the adversarial model, this bound is essentially tight, since
Ashlagi et al. [1] showed that any randomised algorithm achieves a competitive
ratio of $\Omega(\log n/\log\log n)$. Note that the above results assume that
the $n$-point metric is given in advance. When the metric is not known in
advance, Bienkowski et al. proposed a $O(m^{2.46})$-competitive online greedy
algorithm [13] and a $O(m)$-competitive online algorithm based on the primal-
dual method [12], where $m$ denotes the number of requests released. Azar and
Jacob-Fanani [6] later proposed a
$O(m^{\log\frac{3}{2}+\varepsilon})$-competitive greedy algorithm, which is
currently the best deterministic online algorithm. In the special case of a
two-point metric, Emek et al. [19] proposed a 3-competitive greedy algorithm.

Another line of work considered a bipartite variant of MPMD, i.e., the Min-
cost Bipartite Perfect Matching with (linear) Delays (MBPMD), where each
request can be either red or blue, and only two requests of different colours
can be matched into a pair. For MBPMD, Ashlagi et al. [1] presented two
algorithms achieving a competitive ratio of $O(\log n)$ — the first is an
adaptation of Emek et al.’s [18] algorithm to the bipartite case, and the
second is an adaptation of the algorithm proposed by Azar et al. [2]. Besides,
Ashlagi et al. [1] presented a lower bound of $\Omega(\sqrt{\log n/\log\log
n})$ on any randomised algorithm.

The MPMD and MBPMD problems have been investigated in the more general case
when any request can be delayed for a duration $t$ at a cost $f(t)$. Liu et
al. [24] considered the case when $f$ is a convex function, and established a
lower bound $\Omega(n)$ on the competitive ratio of any deterministic
algorithm for Convex-MPMD. Specifically, this bound is obtained for an
$n$-point uniform metric and a delay function of the form $f(t)=t^{\alpha}$
for $\alpha>1$. In this case, they presented a deterministic algorithm that
achieves a competitive ratio of $O(n)$. In the case when $f$ is a concave
function, Azar et al. [7] gave a $O(1)$-competitive (resp. $O(\log
n)$-competitive) deterministic online algorithms for MPMD and MBPMD for a
single-point metric (resp. any metric).

Other classical online problems have been also considered under such delay
setting, such as the online service problem [5, 14, 8], the multi-level
aggregation problem [10, 15, 16, 8], facility location [11, 8, 9], bin packing
[4, 20], set cover [3, 28] and others [25, 22, 9, 28, 17].

##  2 Preliminaries

#### Problem statement.

A _metric space_ $\mathcal{M}=(\mathcal{X},d)$ is a set of points
$\mathcal{X}$ equipped with a distance function
$d:\mathcal{X}\times\mathcal{X}\to\mathbb{R}^{+}$ that satisfies the triangle
inequality. The input for the MPMD problem consists of a sequence $\sigma$ of
$m$ requests ($m$ being an even integer), where each request $r\in\sigma$ is
characterised by its _location_ $\ell(r)\in\mathcal{X}$ and _arrival time_
$t(r)\in\mathbb{R}^{+}$ (w.l.o.g., suppose that no two requests arrive at the
same time). Now, given any solution for an input sequence $\sigma$, let $M$
denote the set of paired requests (i.e., the perfect matching generated for
$\sigma$), and let $s(r)\geq t(r)$ denote the moment when a request $r$ is
matched. Note that if $r$ and $r^{\prime}$ are matched into a pair, i.e.,
$(r,r^{\prime})\in M$, we have $s(r)=s(r^{\prime})$. Using this notation, the
total cost of a solution $(M,s)$ is the sum of its _delay cost_ and its
_connection cost_ defined as follows. The delay cost produced by the solution
is the sum of the delay costs $s(r)-t(r)$ incurred for each request $r$.
Similarly, the connection cost is the sum of distances between all the paired
requests, i.e., $\sum_{(r,r^{\prime})\in M}d(\ell(r),\ell(r^{\prime}))$.

Let ${\rm OPT}(\sigma)$ denote the minimum cost of a feasible solutions for
$\sigma$. Notice that it corresponds to a minimum weight perfect matching for
$\sigma$, where the weight of an edge $(r,r^{\prime})\in\sigma\times\sigma$ is
given by $d(\ell(r),\ell(r^{\prime}))+|t(r)-t(r^{\prime})|$. Indeed, for any
pair ($r,r^{\prime}$) produced by the optimal solution it holds that
$s(r)=s(r^{\prime})=\max\\{t(r),t(r^{\prime})\\}$. This observation implies
that the optimal offline solution can be computed in polynomial time of the
number of requests. In this paper, we are interested in the design of _online_
algorithms for the problem: the decision of matching a pair $(r,r^{\prime})$
at time $t$ only depends on $\\{r\in\sigma:t(r)\leq t\\}$, and this decision
is irrevocable.

#### Stochastic model.

In the stochastic version of MPMD, the goal is to design an online algorithm
that processes a sequence of requests arriving at “random moments”, instead of
being generated by an online adversary. To formalise the notion of random
arrival times, we use the Poisson arrival process: given any point
$x\in\mathcal{X}$, we assume that the requests arrive at $x$ with a Poisson
arrival rate $\lambda_{x}>0$. Recall that an exponential variable $X\sim{\rm
Exp}(\lambda)$ with parameter $\lambda>0$ has a probability density function
$f_{\lambda}(t)=\lambda e^{-\lambda t}$ for $t\geq 0$ and expectation
$\mathbb{E}[X]=1/\lambda$. The exponential distribution may be viewed as a
continuous counterpart of the geometric distribution, which describes the
number of Bernoulli trials necessary for a discrete process to change state
(here, observing a new request on a given point). The exponential distribution
is used for instance in physics to model the time until a radioactive particle
decays, or in queuing theory to model the time it takes for an agent to serve
the request of a customer.

######  Definition 3 (distributed Poisson arrival model).

We say that a (random) _requests sequence_ $\sigma$ follows distributed
Poisson arrival model if the _waiting time_ between any two consecutive
requests arriving at the same point $x\in\mathcal{X}$ follows an _exponential
distribution_ with parameter $\lambda_{x}>0$ and the variables representing
waiting times are mutually independent.

In this paper, when we say that $\sigma$ is _a random request sequence of
length_ $m$, for some integer $m$, we mean that $\sigma$ consists of $m$
requests, and that their arrival times follows the distributed Poisson arrival
model. In this context we measure the performance of our algorithms using the
_ratio-of-expectations_ :

######  Definition 4.

We say that an algorithm ${\rm ALG}$ for MPMD has a ratio-of-expectations
$C\geq 1$, if

$\overline{\lim_{m\to\infty}}\frac{\mathbb{E}_{\sigma}^{m}[{\rm
ALG}(\sigma)]}{\mathbb{E}_{\sigma}^{m}[{\rm OPT}(\sigma)]}\leq C,$

where ${\rm ALG}(\sigma)$ (resp. ${\rm OPT}(\sigma)$) denotes the cost
produced by ${\rm ALG}$ (resp. an optimal offline solution) on the request
sequence $\sigma$, and $\mathbb{E}_{\sigma}^{m}[{\rm ALG}(\sigma)]$ (resp.
$\mathbb{E}_{\sigma}^{m}[{\rm OPT}(\sigma)]$) denotes the expected cost of
${\rm ALG}$ (resp. ${\rm OPT}$) on a random input sequence $\sigma$ consisting
of $m$ requests generated by the Poisson arrival process.

Notice that there are other criteria to measure the performance of stochastic
online algorithms, such as the _expectation-of-ratio_ defined as the expected
value of the ratio ${\rm ALG}(\sigma)/{\rm OPT}(\sigma)$, over all random
inputs $\sigma$; see e.g. [21].

We now present a more analysis-friendly version of the Poisson arrival model,
referred to as the _centralised_ model. To design this equivalent process, we
exploit the two well-known properties of the exponential distribution.

######  Proposition 5 (memoryless property).

If $X$ is an exponential variable with parameter $\lambda$, then for all
$s,t\geq 0$, we have

$\mathbb{P}\left(X>s+t\ |\ X>s\right)=\mathbb{P}(X>t)=e^{-\lambda t}.$

######  Proposition 6.

Given $n$ independent exponential variables $X_{i}\sim{\rm Exp}(\lambda_{i})$
for $i\in\\{1,2,\dots,n\\}$, let $Z:=\min\\{X_{1},X_{2},\dots,X_{n}\\}$ and
let $\lambda:=\sum_{i=1}^{n}\lambda_{i}$. It holds that [style=enumerate](3)
$Z\sim{\rm Exp}(\lambda)$, $\mathbb{P}(Z=X_{i})=\lambda_{i}/\lambda$,
$Z\perp\\{Z=X_{i}\\}$, where $\perp$ denotes independence.

To construct the centralised model, we first assign to each point $x$ a clock
with a timer that goes off at the moment determined by an exponential variable
with parameter $\lambda_{x}$. We define the timers to set themselves
immediately after they ring and start counting the next exponentially-
distributed time interval. Here, we assume that all timers are mutually
independent and independent of the history prior to the time they were set.
Given this setup, we say that a request arrives at point $x$ every time its
timer goes off.

distributed Poisson arrival
model$x$$y$$z$$t_{x}$$Y_{x}^{1}$$Y_{x}^{2}$$\cdots$$t_{y}$$Y_{y}^{1}$$\cdots$$t_{z}$$Y_{z}^{1}$$Y_{z}^{2}$$\cdots$$t$$r_{x}^{1}$$r_{z}^{1}$$r_{y}^{1}$$r_{x}^{2}$$r_{z}^{2}$timers
without
resets$x$$y$$z$$t_{x}$$T_{x}^{x,0}$$T_{x}^{x,1}$$\cdots$$t_{y}$$T_{y}^{y,0}$$\cdots$$t_{z}$$T_{z}^{z,0}$$T_{z}^{z,1}$$\cdots$$t$$r_{x}^{1}$$r_{z}^{1}$$r_{y}^{1}$$r_{x}^{2}$$r_{z}^{2}$
Figure 1: Example showing the correspondence between distributed Poisson
arrival model and exponential timers (without resets). The graph on the right
highlights in blue the waiting times between the consecutive arrivals from the
perspective of the whole metric space.

It is easy to notice that as of now, we have only rephrased the description of
the previous model (see Figure 1, where $Y_{x}^{i+1}$ and $T_{x}^{x,i+1}$ both
represent the waiting time between the $i$-th and the $(i+1)$-th request
arriving at $x$). Timers, though, allow us to reset them at any point (i.e.
stop the current timer and set a new one), obtaining an equivalent stochastic
process. Indeed, by the memoryless property, resetting running timers is
equivalent to letting them continue to run. Using this insight, we can prove
that the following arrival model is equivalent to the one already presented.

######  Definition 7 (centralised Poisson arrival model).

We say that a (random) _requests sequence_ $\sigma$ follows centralised
Poisson arrival model if the _waiting time_ between any two consecutive
requests in the given metric space follows an _exponential distribution_ with
parameter $\lambda(\mathcal{X}):=\sum_{x\in\mathcal{X}}\lambda_{x}$ and each
time a request arrives, the probability of it appearing at point $x$ equals
$\lambda_{x}/\lambda(\mathcal{X})$. We assume that the waiting times and
requests location choices are all mutually independent.

To get a better understanding of how this model relates to timers with resets,
see Figure 2. The graph on the left shows the centralised model where the
waiting time between appearances of the $i$-th and the $(i+1)$-th requests is
determined by the realisation of variable $Y_{i+1}\sim{\rm
Exp}(\lambda(\mathcal{X}))$. On the right, we set the timers $T_{x}^{i}$ for
each point $x$ independently and wait for their minimum to go off. By
Proposition 6, the minimum follows an exponential distribution with parameter
${\rm Exp}(\lambda(\mathcal{X}))$ and has the same appearance distribution
over points as the centralised model.

centralized Poisson arrival
model$x$$y$$z$$t$$r_{1}$$r_{2}$$r_{3}$$r_{4}$$r_{5}$$Y_{1}$$Y_{2}$$Y_{3}$$Y_{4}$$Y_{5}$$\cdots$$t_{x}$$Y_{1}$$Y_{4}$$\cdots$$t_{y}$$Y_{3}$$\cdots$$t_{z}$$Y_{2}$$Y_{5}$$\cdots$timers
with
resets$x$$y$$z$$t$$r_{1}$$r_{2}$$r_{3}$$r_{4}$$r_{5}$$T_{x}^{0}$$T_{z}^{1}$$T_{y}^{2}$$T_{x}^{3}$$T_{z}^{4}$$\cdots$$t_{x}$$T_{x}^{0}$$T_{x}^{1}$$T_{x}^{2}$$T_{x}^{3}$$T_{x}^{4}$$\cdots$$t_{y}$$T_{y}^{0}$$T_{y}^{1}$$T_{y}^{2}$$T_{y}^{3}$$T_{y}^{4}$$\cdots$$t_{z}$$T_{z}^{0}$$T_{z}^{1}$$T_{z}^{2}$$T_{z}^{3}$$T_{z}^{4}$$\cdots$
Figure 2: Example showing the correspondence between the centralised Poisson
arrival model and timers with resets. On the right, a double-headed arrow
represents a timer that went off, while a single-headed arrow means that we
had to reset a timer.

Notice that since both models are equivalent, it gives us another way of
looking at the stochastic process we work with — it is sufficient to define an
arrival rate for the whole metric space and adjust the requests appearance
distribution over the points.

##  3 Constant competitive algorithms

In this section, we introduce two deterministic online algorithms for the MPMD
problem: Greedy and Radius. We formally define the radius of each metric point
which is used to design the Radius algorithm. We present the upper bounds on
the expected cost of our algorithms (Lemmas 11 and 12) and the lower bound on
the expected cost of the optimal offline solution (Lemma 13). We give an
overview of the techniques used to obtain these bounds. Finally, with these
Lemmas, we prove Theorems 1 and 2.

###  3.1 The Greedy algorithm

First, let us present a simple greedy algorithm. Its strategy is pretty
straightforward: once the total waiting time of any two pending requests
exceeds the distance between them, Greedy immediately matches them together.
It is easy to show that this algorithm is well-defined. Indeed, since the
metric space $\mathcal{M}$ is bounded (as it contains a finite number of
points), the waiting time of the last request is bounded by the diameter of
$\mathcal{M}$. Together with the assumption that the input sequence $\sigma$
has an even number of requests, it proves that Greedy outputs a perfect
matching on $\sigma$. Notice that this algorithm works more generally in the
online adversarial model, and additionally that it does not require to know
the metric space or the exponential parameters in advance. For a more formal
description of this greedy procedure, see the pseudo-code of Algorithm 1.

Input: A sequence $\sigma$ of requests.

Output: A perfect matching of the requests.

1 for  _any time $t$_ do

2 if  _there exist pending requests $r,r^{\prime}$ such that
$(t-t(r))+(t-t(r^{\prime}))\geq d(\ell(r),\ell(r^{\prime}))$ _ then

3 match them into a pair with ties broken arbitrarily.

4

Algorithm 1 Greedy

To better understand the algorithm, we can look at its geometrical
interpretation. Here, when a request $r$ appears at some point $x$, a ball
centred at $x$ starts growing with a uniform rate as time passes by. The
radius of this ball represents the delay cost incurred due to leaving $r$
unmatched. Hence, once two balls intersect, the pending requests located at
their centres are paired. Figure 3 shows an example of such a process.

$r_{1}$$t$0123$t$0123$r_{2}$$t$0123Greedy algorithm$t$0123$t$0123 Figure 3: An
example of how Greedy works on a sequence of two requests arriving at times 0
and 0.5 in a 2-point metric space with the distance between the points equal
to 1.5.

The remaining part of this subsection presents a sketch of how to prove the
constant ratio-of-expectations for Greedy (Theorem 1). First, we observe that
for each request served by this algorithm, its connection cost does not exceed
its delay cost. Thus, if we find the upper bound for the latter, we will be
able to estimate the total expected cost of the matching generated by Greedy
on a request sequence $\sigma$. To do so, let us focus on finding the expected
delay cost of a single request $r$ arriving at some point $x\in\mathcal{X}$.
We say that it is matched with a close request if the distance between them is
bounded by some threshold $\rho_{x}$ that we will refer to as a radius. For
now, it suffices to know that this value depends on the arrival location $x$
of $r$ and will be defined later. To introduce formally the radius, we use the
following notation for closed and open balls.

######  Definition 8.

For each point $x\in\mathcal{X}$, let $\overline{B}(x,u)$ (resp.
${B}^{\circ}(x,u)$) denote the set of metric points $y\in\mathcal{X}$ with a
distance no more than (resp. strictly less than) $u$ from $x$.

The next part of the analysis heavily depends on whether there exists a
request arriving after $r$ at any point in $\overline{B}(x,\rho_{x})$ or not.
When the latter happens, we call $r$ a late request and upper bound the cost
of serving it by the highest value possible — the sum of the metric space
diameter and the expected waiting time for the next request to arrive.
Although the estimation may seem exaggerated, it can be proved that only a few
such requests exist. For the first case, when a close request arrives after
$r$, with the right choice of $\rho_{x}$, the expected cost of serving $r$ can
be upper bounded by a constant times the radius. We define radius as follows.
For any subset of points $\mathcal{S}\subseteq\mathcal{X}$, we denote
$\lambda(\mathcal{S}):=\sum_{x\in\mathcal{S}}\lambda_{x}$.

######  Definition 9.

For each point $x\in\mathcal{X}$, define its radius $\rho_{x}$ as the minimum
value $u\geq 0$, such that

$\frac{1}{\lambda(\overline{B}(x,u))}\leq u.$

The idea behind it is that it balances the relationship between the diameter
of $\overline{B}(x,u)$ and the expected waiting time between consecutive
request arrivals within the points of this ball. Indeed, using the information
from the preliminaries, one can show that the latter is equal to the left-hand
side of the inequality. Finally, we note that the radius is well-defined as
the function $u\mapsto 1/\lambda(\overline{B}(x,u))$ is non-increasing and
thus $\rho_{x}\in(0,1/\lambda_{x}]$. See Figure 4 for a pictorial example.

metric space and stochastic
parameters$\rho_{x}$$\rho_{x}^{\prime}$$x$$y$$z$$v$$\lambda_{x}=\frac{1}{6}$$\lambda_{y}=\frac{1}{12}$$\lambda_{z}=\frac{1}{12}$$\lambda_{v}=\frac{1}{3}$$\lambda_{x}=\frac{1}{6}$$\lambda_{y}=\frac{1}{5}$$\lambda_{z}=\frac{1}{3}$$\lambda_{v}=\frac{1}{2}$$d(x,y)=1$$d(x,z)=2$$d(x,v)=4$${\color[rgb]{0.045703125,0.537890625,0.657421875}\definecolor[named]{pgfstrokecolor}{rgb}{0.045703125,0.537890625,0.657421875}f(u)=\dfrac{1}{\lambda\left(\bar{B}(x,u)\right)}}$${\color[rgb]{0.9,0.741796875,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.741796875,0}g(u)=u}$${\color[rgb]{0.369140625,0.671484375,0.140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.369140625,0.671484375,0.140625}f(u)=\dfrac{1}{\lambda\left(\bar{B}(x,u)\right)}}$ball
without border
points$\dfrac{1}{{\color[rgb]{0.045703125,0.537890625,0.657421875}\definecolor[named]{pgfstrokecolor}{rgb}{0.045703125,0.537890625,0.657421875}\lambda_{x}}}$$0$$u$$f(u)$$g(u)$$\rho_{x}$$y$$z$$v$ball
with one border
point$\dfrac{1}{{\color[rgb]{0.369140625,0.671484375,0.140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.369140625,0.671484375,0.140625}\lambda_{x}}}$$0$$u$$f(u)$$g(u)$$\rho_{x}^{\prime}$$y$$z$$v$
Figure 4: When determining the radius for some point $x$, two cases may occur.
First, we have an equality in Definition 9, meaning that the plots of
$f(u)=1/\lambda\left(\overline{B}(x,u)\right)$ and $g(u)=u$ intersect
explicitly (see the graph on the left). Second, the value of $f(u)$ drops
below $g(u)$ when approaching some point on the border of the ball (see the
graph on the right).

By the radius definition, we have the following observation.

######  Observation 10.

Given any point $x\in\mathcal{X}$,

$\frac{1}{\lambda({B}^{\circ}(x,\rho_{x}))}\geq\rho_{x}\geq\frac{1}{\lambda(\overline{B}(x,\rho_{x}))}.$

Here, we present both the upper and the lower bound on the radius, as one of
them is needed to lower bound the expected cost of the optimal offline
solution, and the second one is required to upper bound the expected cost of
our algorithms.

To conclude, let us state the upper bound on the expected cost produced by
Greedy.

######  Lemma 11.

For MPMD in the Poisson arrival model, the expected cost produced by the
Greedy algorithm, over all random sequences consisting of $m$ requests,
satisfies

$\mathbb{E}_{\sigma}^{m}[{\rm
Greedy}(\sigma)]\leq\left(4m\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\rho_{x}\right)+2|\mathcal{X}|\cdot\left(d_{\max}+\frac{1}{\lambda(\mathcal{X})}\right).$

where $d_{\max}:=\max_{x,y\in\mathcal{X}}d(x,y)$ is the diameter of the metric
space.

The last term of the right-hand side describes the cost of serving the late
requests. The first term represents the standard expected cost of serving
requests and is proportional to the length of the sequence $\sigma$. We prove
this lemma in Section 5.

###  3.2 The Radius algorithm

In this subsection, our goal is to improve the performance guarantees of the
Greedy algorithm on stochastic inputs. For this purpose, we design a Radius
algorithm that calculates the radii upfront and uses this information to serve
the requests better. The main idea here is to match any two requests whenever
the closed balls of their locations (with radii defined as in Definition 9)
overlap.

In the geometrical interpretation, whenever a request arrives at some point
$x$, the algorithm directly sets its ball to be $\overline{B}(x,\rho_{x})$.
Hence, once a request $r$ appears, if its location belongs to the closed ball
of any pending request $r^{\prime}$, then the two are matched222Notice that
there exists at most one such request $r^{\prime}$. Otherwise, if at the
moment of its arrival, $r$ belonged to the closed balls of two requests
$r^{\prime}$ and $r^{\prime\prime}$, their balls would intersect. Thus, they
should have been paired before, which leads to a contradiction.. Otherwise, if
there exists another request $r^{\prime\prime}$ within the distance of
$\rho_{\ell(r)}+\rho_{\ell(r^{\prime\prime})}$ from $r$’s location, $r$ can be
matched with any such request. Finally, if no request satisfies the above
conditions, $r$ is temporarily left unmatched. See the pseudo-code shown in
Algorithm 2 for a precise description of Radius. Notice that since Radius
calculates the radii, it needs to know the metric space $(\mathcal{X},d)$ and
the exponential parameters $\\{\lambda_{x}\\}_{x\in\mathcal{X}}$. This is not
an heavy requirement, since in the case of stochastic inputs, by the Law of
large numbers, one can learn in constant time
$O(1/\min_{x\in\mathcal{X}}\lambda_{x})$ an arbitrarily good estimate of the
arrival rates.

Input: A sequence $\sigma=(r_{1},\dots,r_{m})$ of requests, the arrival rate
of each metric point.

Output: A perfect matching of the requests.

1 Compute the radius $\rho_{x}$ for each point $x\in\mathcal{X}$ (Definition
9);

2 $P\leftarrow$ the set of pending requests, initially empty;

3 for  _$i=1$ to $m$_ do

4 let $t=t(r_{i})$ denote the arrival time of the $i$-th request $r_{i}$;

5 if  _there exists a pending request $r^{\prime}\in P$ such that
$d(\ell(r_{i}),\ell(r^{\prime}))\leq\rho_{\ell(r^{\prime})}$_ then

6 match $r_{i}$ and $r^{\prime}$ together, and remove $r^{\prime}$ from $P$.

7 else if  _there exists a pending request $r^{\prime}\in P$ such that
$d(\ell(r_{i}),\ell(r^{\prime}))\leq\rho_{\ell(r^{\prime})}+\rho_{\ell(r_{i})}$_
then

8 match $r_{i}$ and $r^{\prime}$ together, breaking ties arbitrarily, and
remove $r^{\prime}$ from $P$.

9 else

10 add $r_{i}$ in $P$

11

12if  _$P\neq\emptyset$_ then

13 match all requests in $P$ arbitrarily

Algorithm 2 Radius

It turns out that using the radius information directly in the algorithm leads
to a better ratio-of-expectations. Below we present an upper bound on the
expected cost of the Radius solution.

######  Lemma 12.

For MPMD in the Poisson arrival model, the expected cost produced by the
Radius algorithm, over all random sequences consisting of $m$ requests,
satisfies

$\mathbb{E}_{\sigma}^{m}[{\rm
Radius}(\sigma)]\leq\left(2m\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\rho_{x}\right)+\frac{1}{2}\cdot|\mathcal{X}|\cdot
d_{\max}.$

where $d_{\max}:=\max_{x,y\in\mathcal{X}}d(x,y)$ is the diameter of the metric
space.

The formal proof of this lemma can be found in Section 6. Here, we conclude
the algorithm description with an example illustrated in Figure 5.

$\rho_{x}$$\rho_{z}$$x$$z$$d(x,z)=1.5$$\rho_{x}=2$$\rho_{z}=1$metric
space$r_{1}$$r_{2}$$\ell(r_{1})=x$$t(r_{1})=0$$\ell(r_{2})=z$$t(r_{2})=0.5$requests$r_{1}$$t$0123$r_{1}$$r_{2}$$t$0123Radius
algorithm$r_{1}$$r_{2}$$t$0123 Figure 5: An example of how Radius works on a
sequence of two requests.

###  3.3 Lower bound on the optimal offline matching

It remains to present an overview of the lower bounding scheme for the optimal
offline solution of the MPMD problem. Having such a result will enable us to
find the performance ratio for the two algorithms introduced before and show
that they both achieve constant ratio-of-expectations.

The crucial part of the lower bounding process is to analyse each request $r$
in a sequence $\sigma$ separately and observe that two situations can happen
when $r$ is not matched immediately. On one hand, $r$ can be matched early
with some distant request, thus, paying a high connection cost. On the other
hand, it can wait for a closer request to arrive and pay a higher delay cost.
A similar situation takes place when $r$ is paired at the moment of its
arrival with an older request. The only difference then is that we go through
the timeline in the opposite direction.

Let us set the threshold for a request to be considered close to $r$ as the
radius of $r$’s arrival location, i.e., $\rho_{\ell(r)}$. Then, the expected
cost of serving $r$ can be upper bounded by the expected value of the minimum
of three things. The first one is the cost of matching $r$ with the latest
request that has arrived in ${B}^{\circ}(x,\rho_{x})$ before $r$. The second
is equal to the cost of matching $r$ with the earliest request arriving after
it at any point in this ball. Finally, the third one is just the radius
$\rho_{x}$ as it is the lower bound for the connection cost outside the ball.
When we use the stochastic assumption to compute this minimum, we obtain the
following.

######  Lemma 13.

For MPMD in the Poisson arrival model, the expected cost of the optimal
offline solution, over all random sequences consisting of $m$ requests,
satisfies

$\mathbb{E}_{\sigma}^{m}[{\rm OPT}(\sigma)]\geq
m\cdot\frac{1-e^{-2}}{4}\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\rho_{x}.$

We present a detailed proof of this lemma in Section 4.

###  3.4 Proofs of the main theorems

Finally, we prove the two main theorems stated in the introduction.

See 1

###### Proof.

Using the upper bound on Greedy from Lemma 11 and the lower bound on the
optimal offline solution presented in Lemma 13, we obtain

$\begin{split}\overline{\lim_{m\to\infty}}\dfrac{\mathbb{E}_{\sigma}^{m}[{\rm
ALG}(\sigma)]}{\mathbb{E}_{\sigma}^{m}[{\rm OPT}(\sigma)]}&\ \leq\
\lim_{m\to\infty}\dfrac{\left(4m\sum_{x\in\mathcal{X}}\dfrac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\rho_{x}\right)+2|\mathcal{X}|\cdot\left(d_{\max}+\dfrac{1}{\lambda(\mathcal{X})}\right)}{m\cdot\dfrac{1-e^{-2}}{4}\sum_{x\in\mathcal{X}}\dfrac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\rho_{x}}\\\\[4.0pt]
&\ =\
\dfrac{16}{1-e^{-2}}+\lim_{m\to\infty}\dfrac{1}{m}\cdot\dfrac{2|\mathcal{X}|\cdot\left(d_{\max}+\dfrac{1}{\lambda(\mathcal{X})}\right)}{\dfrac{1-e^{-2}}{4}\sum_{x\in\mathcal{X}}\dfrac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\rho_{x}}\
=\ \dfrac{16}{1-e^{-2}},\end{split}$

which concludes the proof. ∎

Analogously, if we refer to Lemma 12, we can prove the following.

See 2

##  4 Lower bound on the optimal offline matching

In this section, we prove Lemma 13 (restated below).

See 13

The main idea of the proof goes as follows. To obtain a lower bound on the
expected cost of the optimal matching over a request sequence $\sigma$, we
analyse each element of $\sigma$ separately. First, we observe that for each
request, the sum of its connection and delay cost is at least equal to the
cost of connecting it to its cheapest neighbour in $\sigma$ (in terms of
connection + delay cost). Then, the core of the proof (Claim 17) consists of
showing that, in expectation, this cost is at least a constant times the
radius of the corresponding point.

Given any input sequence $\sigma$ and any request $r\in\sigma$, we define the
_minimum total cost of $r$ in $\sigma$_ as

$c(\sigma,r):=\min_{r^{\prime}\in\sigma,r^{\prime}\neq
r}\left\\{d(\ell(r),\ell(r^{\prime}))+|t(r)-t(r^{\prime})|\right\\}$

######  Claim 14.

For any input sequence $\sigma$ it holds that ${\rm
OPT}(\sigma)\geq\frac{1}{2}\sum_{r\in\sigma}c(\sigma,r)$.

###### Proof.

Given any pair $(r,r^{\prime})$ that gets matched by ${\rm OPT}$, its
connection cost is $d(\ell(r),\ell(r^{\prime}))$ and its delay cost equals
$|t(r)-t(r^{\prime})|$. By definition, we have $c(\sigma,r)\leq
d(\ell(r),\ell(r^{\prime}))+|t(r)-t(r^{\prime})|$ as well as
$c(\sigma,r^{\prime})\leq d(\ell(r),\ell(r^{\prime}))+|t(r)-t(r^{\prime})|$,
which gives
$d(\ell(r),\ell(r^{\prime}))+|t(r)-t(r^{\prime})|\geq\frac{c(\sigma,r)+c(\sigma,r^{\prime})}{2}$.
Finally, we obtain the claim by summing over all matched pairs in ${\rm
OPT}(\sigma)$. ∎

Before formally stating Claim 17, we need the following two results.

######  Proposition 15.

Let $\sigma=(r_{1},r_{2},\ldots)$ be an infinite sequence of requests
generated by the centralised Poisson process and ordered by their arrival
times. Then, for any point $x\in\mathcal{X}$ and any index $i\geq 1$, the
distribution of the waiting time for a next request to arrive after $r_{i}$ at
some point in a set $S\subseteq\mathcal{X}$, $x\in S$, follows an exponential
distribution with parameter $\lambda(S)$.

###### Proof.

By Definition 7 we know that the waiting times between the consecutive
requests arrivals in $\sigma$ follow an exponential distribution with
parameter $\lambda(\mathcal{X})$ and are independent from the requests
location choices. They are also mutually independent by the arrival model’s
definition.

Notice that, if we look at any point $y\in\mathcal{X}$, the probability that
the $k$-th request, $k\geq 1$, arrives at $y$ is
$\lambda_{y}/\lambda(\mathcal{X})$. Thus, from the perspective of $y$, the
exact distribution of the arrival rates $\lambda$ of the other points does not
matter — it only needs to know the value of
$\lambda(\mathcal{X}\setminus\\{y\\})$ to compute its chances of being chosen.
This means that to find the waiting time for a next request to arrive at any
point in $\mathcal{S}$, we can merge all the points in $\mathcal{S}$ into one
new point $s$ with the parameter $\lambda(\mathcal{S})$.

What remains is to recall that the centralised Poisson process was equivalent
to the model where we used timers and reset them every time a request arrived.
However, we could also decide not to reset a timer. Doing so for the $s$’s
timer implies that the waiting time between $t(r_{i})$ and the arrival of the
next request at $s$ has an exponential distribution with parameter
$\lambda(\mathcal{S})$. ∎

To get a better understanding of the above analysis, see Figure 6. We also
present an elementary proof of this proposition, based only on the centralised
Poisson model, in Appendix A.

timers with resets describing centralised Poisson
model$x$$y$$z$$t_{x}$$T_{x}^{0}$$T_{x}^{1}$$T_{x}^{2}$$T_{x}^{3}$$T_{x}^{4}$$T_{x}^{5}$$T_{x}^{6}$$T_{x}^{7}$$T_{x}^{8}$$\cdots$$t_{y}$$T_{y}^{0}$$T_{y}^{1}$$T_{y}^{2}$$T_{y}^{3}$$T_{y}^{4}$$T_{y}^{5}$$T_{y}^{6}$$T_{y}^{7}$$T_{y}^{8}$$\cdots$$t_{z}$$T_{z}^{0}$$T_{z}^{1}$$T_{z}^{2}$$T_{z}^{3}$$T_{z}^{4}$$T_{z}^{5}$$T_{z}^{6}$$T_{z}^{7}$$T_{z}^{8}$$\cdots$$t$$r_{1}$$r_{2}$$r_{3}$$r_{4}$$r_{5}$$r_{6}$$r_{7}$$r_{8}$$r_{9}$suppressed
resets for point $\bar{x}$ representing
$S=\\{x,y\\}$$x$$y$$z$$T_{x}^{0}$$T_{x}^{1}$$T_{x}^{2}$$T_{x}^{3}$$T_{y}^{0}$$T_{y}^{1}$$T_{y}^{2}$$T_{y}^{3}$$t_{s}$$T_{s}^{s,0}$$T_{s}^{s,1}$$T_{s}^{s,2}$$\cdots$$t_{z}$$T_{z}^{0}$$T_{z}^{1}$$T_{z}^{2}$$T_{z}^{3}$$T_{z}^{4}$$T_{z}^{5}$$T_{z}^{6}$$T_{z}^{7}$$T_{z}^{8}$$\cdots$
Figure 6: An example showing the main idea presented in the proof of
Proposition 15. Here, to analyse the waiting time between consecutive arrivals
on points $x$, $y$, we define new timers $T_{s}^{s,i}$ for the sum of these
point.

######  Claim 16.

Given any $a>0$ and an exponential variable $Y\sim{\rm Exp}(\mu)$,
$\mathbb{E}[\min\\{Y,a\\}]=\frac{1-e^{-\mu a}}{\mu a}\cdot a$.

###### Proof.

We simply calculate the expected value obtaining

$\mathbb{E}[\min\\{Y,a\\}]=\int_{0}^{a}t\cdot\mu e^{-\mu
t}dt+\int_{a}^{\infty}a\cdot\mu e^{-\mu t}dt=\left[-(t+\frac{1}{\mu})e^{-\mu
t}\right]_{0}^{a}+\left[-ae^{-\mu t}\right]_{a}^{\infty}=\frac{1-e^{-\mu
a}}{\mu a}\cdot a,$

which ends the proof. ∎

Now, let us present the core component needed to prove Lemma 13.

######  Claim 17.

Given a sequence $\sigma$, we order the requests in
$\sigma=(r_{1},\dots,r_{m})$ according to their arrival times. Then, for any
point $x\in\mathcal{X}$ and any index $i$ such that $1\leq i\leq m$, the
expected minimum cost of the $i$-th request $r_{i}$ in a random sequence
$\sigma$, assuming that $r_{i}$ is located on $x$, is

$\mathbb{E}_{\sigma}^{m}[c(\sigma,r_{i})\mid\ell(r_{i})=x]\geq\frac{1-{e}^{-2}}{2}\cdot\rho_{x}.$

###### Proof.

To facilitate the proof, we first extend every random request sequence
$\sigma=(r_{1},\dots,r_{m})$ by some dummy random requests $r_{j}$ for $j\leq
0$ and $j\geq m$ to get an _extended_ random sequence

$\overline{\sigma}=(\dots,r_{-2},r_{-1},r_{0},r_{1},\dots,r_{m-1},r_{m},r_{m+1},\dots).$

To generate requests before $r_{1}$ and after $r_{m}$ we use the centralised
Poisson arrival model (i.e., for every integer $j$,
$(t(r_{j+1})-t(r_{j}))\sim{\rm Exp}(\lambda(\mathcal{X}))$ and
$\mathbb{P}(\ell(r_{j})=y)=\lambda_{y}/\lambda(\mathcal{X})$ for all
$y\in\mathcal{X}$). This implies that in the extended sequence of requests,
given any point $y\in\mathcal{X}$, with probability one there exist indexes
$j\leq 0$ and $j^{\prime}\geq m+1$ satisfying
$\ell(r_{j})=\ell(r_{j^{\prime}})=y$.

For an extended random sequence $\overline{\sigma}$, we define its truncation
$\overline{\sigma}_{m}:=(r_{1},\dots,r_{m})$. Remark that the probability
distribution of the truncated extended random request is identical to the
original distribution of the random sequences of $m$ requests. Moreover, the
minimum cost $c(\sigma,r_{j})$ of any request $r_{j}$, with
$j\in\\{1,\dots,m\\}$, can only decrease, i.e.,
$c(\overline{\sigma},r_{j})\leq c({\sigma},r_{j})$ where
$\sigma=\overline{\sigma}_{m}$. Hence, we have

$\mathbb{E}_{\sigma}^{m}[c(\sigma,r_{i})\mid\ell(r_{i})=x]\geq\mathbb{E}_{\overline{\sigma}}[c(\overline{\sigma},r_{i})\mid\ell(r_{i})=x].$

Notice that the conditional expected minimum cost of each $r_{j}$ arriving at
any point $x$ in a extended random sequence is now the same for all request of
the sequence, i.e., for any $j,j^{\prime}\in\\{0,1,\dots,m\\}$,

$\mathbb{E}_{\overline{\sigma}}[c(\overline{\sigma},r_{j})\mid\ell(r_{j})=x]=\mathbb{E}_{\overline{\sigma}}[c(\overline{\sigma},r_{j^{\prime}})\mid\ell(r_{j^{\prime}})=x].$

In particular, to prove the claim, we only need to establish a bound on the
conditional expected cost of serving the request zero, i.e., we need to show
that

$\mathbb{E}_{\overline{\sigma}}[c(\overline{\sigma},r_{0})\mid\ell(r_{0})=x]\geq\frac{1-{e}^{-2}}{2}\cdot\rho_{x}.$
(1)

To prove this bound, consider an extended sequence $\overline{\sigma}$ with
$\ell(r_{0})=x$. W.l.o.g., we also assume that $t(r_{0})=0$ as it can be
achieved by shifting all arrival times by the same constant. Define $W^{-}$
(resp. $W^{+}$) as the (random) time duration between the arrival of the last
request before $r_{0}$ (resp. first request after $r_{0}$) arriving at any
point $y\in B^{\circ}(x,\rho_{x})$ and the arrival of $r_{0}$. Formally,

$W^{-}:=\min_{j<0}\left\\{-t(r_{j}):d(\ell(r_{j}),x)<\rho_{x}\right\\}\geq
0\quad\text{ and }\quad
W^{+}:=\min_{j>0}\left\\{t(r_{j}):d(\ell(r_{j}),x)<\rho_{x}\right\\}\geq 0.$

Since we work with extended sequences, both $W^{+}$ and $W^{-}$ are finite.
Hence, we can use them to bound the value of $c(\overline{\sigma},r_{0})$.
Intuitively, we lower bound the (connection + delay) cost of the requests far
from $x$ by their connection cost, and the total cost of the requests close to
$x$ by their delay cost. More precisely,

$\displaystyle c(\overline{\sigma},r_{0})$ $\displaystyle=$
$\displaystyle\min_{j\neq 0}\big{\\{}d(x,\ell(r_{j}))+|t(r_{j})|\big{\\}}$ (2)
$\displaystyle\geq$ $\displaystyle\min\Big{\\{}\min_{j\neq
0}\left\\{|t(r_{j})|:d(\ell(r_{j}),x)<\rho_{x}\right\\},\rho_{x}\Big{\\}}$
$\displaystyle=$
$\displaystyle\min\Big{\\{}\min_{j<0}\left\\{-t(r_{j}):d(\ell(r_{j}),x)<\rho_{x}\right\\},\min_{j>0}\left\\{t(r_{j}):d(\ell(r_{j}),x)<\rho_{x}\right\\},\rho_{x}\Big{\\}}$
$\displaystyle=$ $\displaystyle\min\big{\\{}W^{-},W^{+},\rho_{x}\big{\\}}$
$\displaystyle=$
$\displaystyle\min\big{\\{}\min\\{W^{-},W^{+}\\},\rho_{x}\big{\\}},$

where the first inequality is obtained by lower bounding
$d(x,\ell(r_{j}))+|t(r_{j})|$ by $\rho_{x}$ when
$d(x,\ell(r_{j}))\geq\rho_{x}$, and by $|t(r_{j})|$ otherwise.

We claim that $W^{-}$ and $W^{+}$ are mutually independent and follow the same
exponential distribution ${\rm Exp}(\lambda(B^{\circ}(x,\rho_{x})))$. To prove
it, let us recall that we work with the centralised Poisson arrival model.
Thus, we can say that $W^{+}$ (resp. $W^{-}$) depends on the waiting times and
arrival location choices after (resp. before) $t=0$. Since the variables
representing history before $t=0$ in our model are independent from those
representing history after $t=0$, so are $W^{-}$ and $W^{+}$. It is also easy
to prove that $W^{+}$ has an exponential distribution with parameter
$\lambda(B^{\circ}(x,\rho_{x}))$ — it follows straightforward from Proposition
15. However, if we look at the timeline for $\overline{\sigma}$ and go from
$t=0$ to $-\infty$, we can once again use Proposition 15 for the sequence
$(r_{0},r_{-1},\dots)$. In this way, we prove that the distribution of $W^{-}$
is also exponential with parameter $\lambda(B^{\circ}(x,\rho_{x}))$.

Now, thanks to Proposition 6, we immediately have

$\min\\{W^{-},W^{+}\\}\sim{\rm Exp}(2\lambda(B^{\circ}(x,\rho_{x}))).$

By inequality (2) and Claim 16 (with $a=\rho_{x}$,
$\mu=2\lambda(B^{\circ}(x,\rho_{x}))$), it follows that

$\mathbb{E}_{\overline{\sigma}}[c(\overline{\sigma},r_{0})\mid\ell(r_{0})=x]\geq\mathbb{E}_{\overline{\sigma}}\Big{[}\min\big{\\{}\min\\{W^{-},W^{+}\\},\rho_{x}\big{\\}}\Big{]}=\frac{1-e^{-2\lambda(B^{\circ}(x,\rho_{x}))\cdot\rho_{x}}}{2\lambda(B^{\circ}(x,\rho_{x}))\cdot\rho_{x}}\cdot\rho_{x}.$

It is easy to check that function $t\mapsto\frac{1-e^{-t}}{t}$ is strictly
decreasing. Together with Observation 10 it guarantees that
$\lambda(B^{\circ}(x,\rho_{x}))\cdot\rho_{x}\leq 1$ and thus

$\frac{1-e^{-2\lambda(B^{\circ}(x,\rho_{x}))\cdot\rho_{x}}}{2\lambda(B^{\circ}(x,\rho_{x}))\cdot\rho_{x}}\geq\frac{1-e^{-2}}{2}.$

Hence,

$\mathbb{E}_{\overline{\sigma}}[c(\overline{\sigma},r_{0})\mid\ell(r_{0})=x]\geq\frac{1-e^{-2}}{2}\cdot\rho_{x},$

which concludes the proof of inequality (1) and, what follows, the proof of
Claim 17. ∎

Finally, we prove Lemma 13.

###### Proof of Lemma 13.

Let $\sigma=(r_{1},\dots,r_{m})$ be a sequence of request sorted in an
increasing order of their arrival times. We have

$\displaystyle\mathbb{E}_{\sigma}^{m}[{\rm OPT}(\sigma)]$
$\displaystyle\geq\mathbb{E}_{\sigma}^{m}\left[\frac{1}{2}\sum_{i=1}^{m}c(\sigma,r_{i})\right]$
(Claim 14)
$\displaystyle=\frac{1}{2}\sum_{i=1}^{m}\mathbb{E}_{\sigma}^{m}[c(\sigma,r_{i})]$
(linearity of expectation)
$\displaystyle=\frac{1}{2}\sum_{i=1}^{m}\sum_{x\in\mathcal{X}}\mathbb{P}_{\sigma}(\ell(r_{i})=x)\cdot\mathbb{E}_{\sigma}^{m}[c(\sigma,r_{i})\mid\ell(r_{i})=x]$
$\displaystyle\geq\frac{1}{2}\sum_{i=1}^{m}\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\frac{1-{e}^{-2}}{2}\cdot\rho_{x}$
(Claim 17)
$\displaystyle=m\cdot\frac{1-e^{-2}}{4}\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\rho_{x}.$

This concludes the proof. ∎

##  5 Upper bound on the Greedy solution

In this section, we prove Lemma 11 (restated below) that establishes an upper
bound on the cost rate of the Greedy algorithm for stochastic inputs.

See 11

To prove this upper bound, we first observe that the total connection cost of
the Greedy solution is at most equal to its total delay cost, and then we
bound the latter.

Given any input sequence $\sigma$, let $(M,s)$ denote the solution output by
the Greedy algorithm, where $M$ is the set of matched pairs of request, and
$s$ is the service times of the requests. The waiting time of a request
$r\in\sigma$ is denoted by $w(r):=s(r)-t(r)$. Greedy matches two requests $r$
and $r^{\prime}$ when the sum of their delay cost $w(r)+w(r^{\prime})$ is at
least equal to their distance $d(\ell(r),\ell(r^{\prime}))$. In particular,
when summing over all requests we obtain:

######  Claim 18.

For any input sequence $\sigma$, the cost of the solution returned by the
Greedy algorithm is at most twice its total delay cost, i.e.,

${\rm Greedy}(\sigma)\leq 2\sum_{r\in\sigma}w(r).$

We now focus on bounding the waiting time of each request. To do this, we
distinguish two types of requests. For each request $r\in\sigma$, we define
$t^{\prime}(r):=t(r)+\rho_{\ell(r)}$, and we say that $r$ is a _late_ request
if there are no requests $r^{\prime}\in\sigma$ requested at a time
$t(r^{\prime})>t^{\prime}(r)$ such that
$d(\ell(r^{\prime}),\ell(r))\leq\rho_{\ell(r)}$. Otherwise, we say that $r$ is
a _nice_ request, and we define

$Y^{\text{nice}}_{r}:=\min_{r^{\prime}\in\sigma}\left\\{t(r^{\prime})-t^{\prime}(r)\mid
t(r^{\prime})>t^{\prime}(r)\text{ and
}d(\ell(r^{\prime}),\ell(r))\leq\rho_{\ell(r)}\right\\}.$

We bound the waiting time of nice requests as follows:

######  Claim 19.

For each nice request $r\in\sigma$, we have
$w(r)\leq\rho_{\ell(r)}+Y^{\text{nice}}_{r}$.

###### Proof.

Let $r$ be any nice request in $\sigma$ and let $r^{\prime}\in\sigma$ be the
first request such that $t(r^{\prime})>t^{\prime}(r)$ and
$d(\ell(r^{\prime}),\ell(r))\leq\rho_{\ell(r)}$, i.e., such that
$t(r^{\prime})-t(r)=\rho_{\ell(r)}+Y^{\text{nice}}_{r}$.

If $r$ has already been matched at time $t(r^{\prime})$ then it means that
$w(r)\leq\rho_{\ell(r)}+Y_{r}$. Otherwise, we claim that $r$ and $r^{\prime}$
are matched together by the Greedy algorithm at time $t=t(r^{\prime})$.
Indeed, we have
$(t-t(r))+(t-t(r^{\prime}))=\rho_{\ell(r)}+Y_{r}>\rho_{\ell(r)}\geq
d(\ell(r^{\prime}),\ell(r))$, so the greedy criteria is satisfied by the pair
$(r,r^{\prime})$. Suppose for a contradiction that $r^{\prime}$ is matched at
time $t$ with another pending request $r^{\prime\prime}$. It is necessary
because $t-t(r^{\prime\prime})\geq
d(\ell(r^{\prime}),\ell(r^{\prime\prime}))$. With the triangle inequality, we
obtain

$(t-t(r))+(t-t(r^{\prime\prime}))>d(\ell(r),\ell(r^{\prime}))+d(\ell(r^{\prime}),\ell(r^{\prime\prime}))\geq
d(\ell(r),\ell(r^{\prime\prime})).$

This means that $r$ and $r^{\prime\prime}$ should have been matched together
before the arrival of $r^{\prime}$, which leads to a contradiction. ∎

We now bound the total delay time induced by late requests. Unfortunately, the
waiting time of a late request can possibly be as large as the diameter
$d_{\max}=\max_{x,y\in\mathcal{X}}d(x,y)$ of the metric space. However, we
show that there are only constantly many such requests. Let $t(r_{m})$ denote
the arrival time of the last request in $\sigma$. For any late request $r$, we
define $Y^{\text{late}}_{r}$ as follows:

  * -

if $t(r)+d_{\max}\geq t(r_{m})$, then $Y^{\text{late}}_{r}:=0$,

  * -

otherwise
$Y^{\text{late}}_{r}:=\min_{r^{\prime}\in\sigma}\left\\{t(r^{\prime})-(t(r)+d_{\max})\mid
t(r^{\prime})>t(r)+d_{\max}\right\\}$.

######  Claim 20.

For any point $x\in\mathcal{X}$, there is at most one late request located on
$x$. In particular, there are at most $|\mathcal{X}|$ late requests. Moreover,
for each late request $r$, we have $w(r)\leq d_{\max}+Y^{\text{late}}_{r}$.

###### Proof.

Let $r$ and $r^{\prime}$ be two requests such that $\ell(r)=\ell(r^{\prime})$
and $t(r)<t(r^{\prime})$. Suppose that when the request $r^{\prime}$ is
processed by the Greedy algorithm, $r$ is still unmatched. Then,
$0=d(\ell(r),\ell(r^{\prime}))\leq\rho_{\ell(r)}+\rho_{\ell(r^{\prime})}$, and
the algorithm matches these requests together. This shows that $r$ cannot
become a pending request, and, in particular, it is not a late request.

We now show the second part of the statement. Let $r$ be any late request. If
$t(r)+d_{\max}\geq t(r_{m})$, then at time $t=t(r)+d_{\max}$, all the requests
in $\sigma$ already arrived. Thus, either $r$ has already been matched, or
there exists at least one other pending request $r^{\prime}$ (as we assume
that the total number of requests is even). Since $t-t(r)=d_{\max}\geq
d(\ell(r),\ell(r^{\prime}))$, the Greedy algorithm matches $r$ and
$r^{\prime}$ at time $t$, which implies that $w(r)=d_{\max}$. Otherwise, we
have $t(r)+d_{\max}<t(r_{m})$. By the definition of $Y^{\text{late}}_{r}$, the
next request $r^{\prime}$ in $\mathcal{X}$ arrives at time
$t=t(r)+d_{\max}+Y^{\text{late}}_{r}$. Once again, either $r$ has already been
matched at time $t$ (and its waiting time is at most
$d_{\max}+Y^{\text{late}}_{r}$), or $r$ is matched with $r^{\prime}$ by the
same argument. In any case, we have proved that $w(r)\leq
d_{\max}+Y^{\text{late}}_{r}$. ∎

We now use stochastic assumptions to upper bound the expected cost of the
solution.

###### Proof of Lemma 11.

Let $\sigma=(r_{1},\dots,r_{m})$ be a random sequence of $m$ requests, where
requests are ordered with increasing arrival times.

We first bound the expected delay cost induced by late requests. Suppose that
the $i$-th request of the sequence, $r_{i}$, is late and is located on a point
$x\in\mathcal{X}$. Using Definition 7, we know that when $\sigma$ is a random
sequence generated by the Poisson arrival process, the (conditional) random
variable $Y^{\text{late}}_{r}$ follows an exponential distribution of
parameter $\lambda(\mathcal{X})$. In particular, we obtain

$\mathbb{E}_{\sigma}^{m}[w(r_{i})\mid r_{i}\text{ is late and
}\ell(r_{i})=x]\leq d_{\max}+\frac{1}{\lambda(\mathcal{X})}.$

Since the expectation does not depend on point $x$, and since there are at
most $|\mathcal{X}|$ late requests, the total delay cost induced by the late
requests is in expectation:

$\mathbb{E}_{\sigma}^{m}\left[\sum_{\begin{subarray}{c}i=1\\\ r_{i}\text{ is
late}\end{subarray}}^{m}w({r_{i}})\right]\leq|\mathcal{X}|\cdot\left(d_{\max}+\frac{1}{\lambda(\mathcal{X})}\right).$

When $r_{i}$ is a nice request located on $x\in\mathcal{X}$, by Proposition
15, the (conditional) random variable $Y^{\text{nice}}_{r}$ follows an
exponential distribution of parameter
$\sum_{y\in\mathcal{X}}\\{\lambda_{y},d(x,y)\leq\rho_{x}\\}$. Using
Observation 10 we obtain:

$\mathbb{E}_{\sigma}^{m}[w(r_{i})\mid r_{i}\text{ is nice and
}\ell(r_{i})=x]=\rho_{x}+1/\lambda(\overline{B}(x,\rho_{x}))\leq\rho_{x}+\rho_{x}=2\rho_{x}.$

As we observed in Definition 7, the probability the the $i$-th request of the
(random) sequence is located on $x$ is equal to
$\lambda_{x}/\lambda(\mathcal{X})$. Thus, the total delay cost induced by nice
requests is

$\displaystyle\mathbb{E}_{\sigma}^{m}\left[\sum_{\begin{subarray}{c}i=1\\\
r_{i}\text{ is nice}\end{subarray}}^{m}w({r_{i}})\right]$
$\displaystyle\leq\sum_{i=1}^{m}\sum_{x\in\mathcal{X}}\mathbb{P}(r_{i}\text{
is nice and }\ell(r_{i})=x)\cdot\mathbb{E}_{\sigma}^{m}\left[w({r_{i}})\mid
r_{i}\text{ is nice and }\ell(r_{i})=x\right]$
$\displaystyle\leq\sum_{i=1}^{m}\sum_{x\in\mathcal{X}}\mathbb{P}(\ell(r_{i})=x)\cdot
2\rho_{x}$
$\displaystyle\leq\sum_{i=1}^{m}\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot
2\rho_{x}$
$\displaystyle=m\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot
2\rho_{x}.$

Finally, putting everything together, we obtain the expected bound:

$\displaystyle\mathbb{E}_{\sigma}^{m}\left[{\rm Greedy}(\sigma)\right]$
$\displaystyle\leq\mathbb{E}_{\sigma}^{m}\left[2\sum_{i=1}^{m}w({r_{i}})\right]$
(Claim 18)
$\displaystyle=2\cdot\mathbb{E}_{\sigma}^{m}\left[\sum_{\begin{subarray}{c}i=1\\\
r_{i}\text{ is
nice}\end{subarray}}^{m}w({r_{i}})\right]+2\cdot\mathbb{E}_{\sigma}^{m}\left[\sum_{\begin{subarray}{c}i=1\\\
r_{i}\text{ is late}\end{subarray}}^{m}w({r_{i}})\right]$
$\displaystyle\leq\left(4m\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\rho_{x}\right)+2|\mathcal{X}|\cdot\left(d_{\max}+\frac{1}{\lambda(\mathcal{X})}\right).$

This concludes the proof. ∎

##  6 Upper bound on the Radius solution

In this section, we prove Lemma 12 (restated below) that establishes an upper
bound on the expected cost of the Radius algorithm.

See 12

To bound the total cost of the solution produced by the Radius, we separately
analyse the delay cost and the connection cost. To bound the connection cost
we differentiate two types of edges (pairs matched by the algorithm). Let $M$
denote the matching produced by the Radius algorithm on the input sequence
$\sigma$. Let us call $e\in M$ a _nice_ edge333Notice that the current
definition differs from the previous section. if there the corresponding
matched pair was created during the main loop of the algorithm, i.e., before
the arrival time of the last request in $\sigma$. Otherwise, we call this edge
_late_. Similarly, a request is called _nice_ if it is an endpoint of a nice
edge, and _late_ otherwise. Intuitively, since the late requests are matched
arbitrarily by the Radius algorithm, the connection cost induced by each of
these late edge can possibly be as large as the diameter of the metric space.
Fortunately, we show that there are only a constant number of them (i.e.,
independent from $m$).

######  Claim 21.

For any point $x\in\mathcal{X}$, there is at most one late request located on
$x$. In particular, there are at most $|\mathcal{X}|/2$ late edges.

###### Proof.

Let $r$ and $r^{\prime}$ be two requests such that $\ell(r)=\ell(r^{\prime})$
and $t(r)<t(r^{\prime})$. Suppose that when the request $r^{\prime}$ is
processed by the radius algorithm, $r$ is still unmatched. Then,
$0=d(\ell(r),\ell(r^{\prime}))\leq\rho_{\ell(r)}+\rho_{\ell(r^{\prime})}$, and
the algorithm matches these requests together. This shows that $r$ cannot
become a pending request, and in particular, it is not a late request. ∎

We now bound the connection cost of the solution induced by nice edges. Two
nice requests are matched together by the Radius algorithm if and only if
their distance is at most the sum of their radii. By summing over all the nice
edges, we obtain:

######  Claim 22.

For any input sequence $\sigma$, the connection cost induced by all nice edges
is at most $\sum_{r\in\sigma}\rho_{\ell(r)}$.

We now bound the total delay cost. Let $t(r_{m})$ denote the arrival time of
the last request of $\sigma$, which correspond to the time at which all
remaining pending (late) requests are matched together by the Radius
algorithm. Let $r$ be any request in $\sigma$. We define $Y_{r}$ as the
duration between the arrivals of $r$ and the first request $r^{\prime}$ that
appears on a point of $\overline{B}(\ell(r),\rho_{\ell(r)})$ after $r$. If
there is no such request $r^{\prime}\in\sigma$, then we set
$Y_{r}:=t(r_{m})-t(r)$. Formally:

$Y_{r}:=\min\left\\{t(r_{m})-t(r),\min_{r^{\prime}\in\sigma}\left\\{t(r^{\prime})-t(r)\mid
t(r^{\prime})>t(r)\text{ and
}d(\ell(r^{\prime}),\ell(r))\leq\rho_{\ell(r)}\right\\}\right\\}$

######  Claim 23.

Each request $r$ in $\sigma$ is delayed by the Radius algorithm for a time at
most equal to $Y_{r}$.

###### Proof.

Let $r$ be any request in $\sigma$, and assume that $r$ is located on point
$x=\ell(r)$. When $r$ is processed by the Radius algorithm, then either $r$ is
matched immediately with a pending request, and in that case $r$ has not been
delayed, or it becomes a pending request. For the second case, let
$r^{\prime}\in\sigma$ be the first request arriving after $r$ at a point $y$
at distance at most $\rho_{x}$ from $x$. If such a request does not exist,
then in the worst case, $r$ is matched at the very end and thus is delayed for
a time $t(r_{m})-t(r)=Y_{r}$. Otherwise, either $r$ was already matched when
$r^{\prime}$ arrived — and then $r$ was delayed for a duration at most
$t(r^{\prime})-t(r)=Y_{r}$ — or, we claim that $r$ and $r^{\prime}$ are
matched together by the Radius algorithm. Indeed, assume for a contradiction
that $r$ and $r^{\prime}$ are not matched together. Since
$d(x,y)\leq\rho_{x}$, it is necessarily because $r$ is matched with another
pending request $r^{\prime\prime}$ located on a point $z$, such that
$d(y,z)\leq\rho_{z}$. But then, by the triangle inequality, we have
$d(x,z)\leq d(x,y)+d(y,z)\leq\rho_{x}+\rho_{z}$ (see Figure 7 for an example).
This is impossible: the Radius algorithm would have matched $r$ and
$r^{\prime\prime}$ together before the arrival of $r^{\prime}$. Thus, in any
of these cases, $r$ is delayed for a time at most $Y_{r}$. ∎

$r^{\prime}$$r$$r^{\prime\prime}$$r^{\prime}$$r$possible scenarios for
Radius$r^{\prime}$$r$$r^{\prime\prime}$$r^{\prime}$$r$$r^{\prime\prime}$impossible
scenario Figure 7: Example scenarios for the arrival of a new request
$r^{\prime}$ during the Radius execution. Firstly, $\ell(r^{\prime})$ can
belong to some pending request’s ball. Secondly, the ball defined for
$r^{\prime}$ can intersect other requests’ balls. However, by the definition
of Radius, $\ell(r^{\prime})$ cannot belong to the ball of more than one
pending request.

Finally, we prove Lemma 12.

###### Proof of Lemma 12.

Let $\sigma$ be a sequence of $m$ requests, and let $M$ denote the perfect
matching output by the Radius algorithm. We split it into two sets
$M_{\text{nice}}$ and $M_{\text{late}}$ of nice and late edges, respectively.
The total cost ${\rm Radius}(\sigma)$ of the solution is equal to the sum
${\rm CC}(M_{\text{nice}})+{\rm CC}(M_{\text{late}})+{\rm DC}$ of the
connection cost ${\rm CC}(M_{\text{nice}})$ induced by the nice edges, the
connection cost ${\rm CC}(M_{\text{late}})$ induced by the late edges and the
total delay cost ${\rm DC}$.

By Claim 21, there are at most $|\mathcal{X}|/2$ late edges.

${\rm CC}(M_{\text{late}})\leq\frac{1}{2}\cdot|\mathcal{X}|\cdot d_{\max}.$
(3)

This bound is valid for any sequence, so, in particular, it is also valid in
expectation.

By Claim 22, we have ${\rm
CC}(M_{\text{nice}})\leq\sum_{r\in\sigma}\rho_{\ell(r)}$. Thus, taking the
average over all random sequences $\sigma=(r_{1},\dots,r_{m})$ consisting of
$m$ requests, we obtain

$\displaystyle\mathbb{E}_{\sigma}^{m}\left[{\rm CC}(M_{\text{nice}})\right]$
$\displaystyle\leq\mathbb{E}_{\sigma}^{m}\left[\sum_{r\in\sigma}\rho_{\ell(r)}\right]=\sum_{i=1}^{m}\sum_{x\in\mathcal{X}}\rho_{x}\cdot\mathbb{P}(\ell(r_{i})=x)=\sum_{i=1}^{m}\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\rho_{x}$
$\displaystyle\leq
m\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\rho_{x}.$
(4)

We now show that total delay cost is in expectation at most

$\mathbb{E}_{\sigma}^{m}[{\rm DC}]\leq
m\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\rho_{x}.$
(5)

For each point $x\in\mathcal{X}$, let $W_{x}\sim{\rm
Exp}(\lambda(\overline{B}(x,\rho_{x})))$ be an exponential variable with
parameter
$\lambda(\overline{B}(x,\rho_{x}))=\sum_{y\in\overline{B}(x,\rho_{x})}\lambda_{y}$.
Let us consider a random sequence $\sigma=(r_{1},\dots,r_{m})$ ordered by
increasing arrival times, and let us assume that the $i$-th request $r_{i}$ is
located at $x$. Then, by Proposition 15, the (random) variable $Y_{r}$, as
defined before Claim 23, follows the same distribution as
$\min\\{W_{x},t(r_{m})-t(r_{i})\\}$. Thus, using Claim 23, we prove inequality
(5) as follows:

$\displaystyle\mathbb{E}_{\sigma}^{m}\left[{\rm DC}\right]$
$\displaystyle\leq\mathbb{E}_{\sigma}^{m}\left[\sum_{i=1}^{m}Y_{r_{i}}\right]$
(Claim 23)
$\displaystyle=\sum_{i=1}^{m}\sum_{x\in\mathcal{X}}\mathbb{P}(\ell(r_{i})=x)\cdot\mathbb{E}_{\sigma}^{m}\left[Y_{r_{i}}\mid\ell(r_{i})=x\right]$
(linearity of expectation)
$\displaystyle=\sum_{i=1}^{m}\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\mathbb{E}\left[\min\\{W_{x},t(r_{m})-t(r_{i})\\}\right]$
$\displaystyle\leq\sum_{i=1}^{m}\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\mathbb{E}\left[W_{x}\right]$
$\displaystyle\leq\sum_{i=1}^{m}\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\rho_{x}$
(Observation 10)
$\displaystyle=m\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\rho_{x}.$

Finally, we obtain the bound claimed in Lemma 12, by summing equations (3),
(4) and (5). This concludes the proof. ∎

##  7 Extension to general delay costs

In this section, we study a generalisation of the MPMD problem where the delay
cost function is not required to be linear. In this version of the problem,
referred to as $f$-MPMD, the decision of whether to match a request can be
postponed for time $t$ at a delay cost of $f(t)$, where $f$ is the _delay cost
function_. We require this function to be _positive_ (otherwise some solutions
may have negative value), and _non-decreasing_. In Appendix B, we show that
w.l.o.g., we can assume $f(0)=0$, i.e., if a request is directly matched at
its arrival time, no delay cost is incurred.

This more general version of MPMD have been investigated for the classic
online adversarial model among others by Azar et al. [7] and Liu et al. [24].
Their works suggests that in general, the $f$-MPDM problem is even more
challenging than the original MPMD problem. For instance, in [7], Azar et al.
considered a special type of concave delay cost function, and showed that even
for the single-point metric, obtaining a constant competitive algorithm is a
non-trivial task (whereas for the linear case, the optimal algorithm simply
matches two consecutive requests). Liu et al. [24] showed that under some
natural requirements for function $f$, any deterministic online algorithm for
$f$-MPMD on a $k$-points metric must have a competitive ratio $\Omega(k)$.

In the online stochastic Poisson arrival model, we show in Theorem 25 that our
Greedy and Radius algorithms for MPMD can be adapted to $f$-MPMD, and that
their corresponding ratios-of-expectations remain a constant, which depends on
$f$.

The adaptation of the Greedy algorithm for $f$-MPMD is quite straightforward:
when the sum of the delay cost of two pending requests exceeds their distance,
match them together, i.e., match pending requests $r$ and $r^{\prime}$ at time
$t$ whenever $f(t-t(r))+f(t-t(r^{\prime}))\geq d(\ell(r),\ell(r^{\prime}))$.

The Radius algorithm works in the general case exactly as in the linear case,
but using the following generalised definition of radius.

######  Definition 24.

Given the positive and non-decreasing delay cost function $f$, for any point
$x\in\mathcal{X}$, define its radius $\rho_{x}$ as the smallest value
$u\in\mathbb{R}^{+}\cup\\{\infty\\}$ such that

$u\geq\mathbb{E}[f(\overline{W}(x,u))],$

where $\overline{W}(x,u)$ is an exponential variable of parameter
$\lambda(\overline{B}(x,u)):=\sum_{y\in\mathcal{X}:d(x,y)\leq u}\lambda_{y}$.

Since functions $u\mapsto\lambda(\overline{B}(x,u))$ and $f$ are both non-
decreasing, the function $u\mapsto\mathbb{E}[f(\overline{W}(x,u))]$ is non-
increasing. This implies that the radius of each point is well-defined and
unique. Moreover, since
$\mathbb{E}[\overline{W}(x,u))]=1/\lambda(\overline{B}(x,u))$, in the case
when $f(t)=t$, this definition coincides with our initial Definition 9.
Similarly as presented in Observation 10, it is easy to see that
$\mathbb{E}[f({W}^{\circ}(x,\rho_{x}))]\geq\rho_{x}$, where
${W}^{\circ}(x,\rho_{x})$ is a random variable of parameter
$\lambda({B}^{\circ}(x,\rho_{x})):=\sum_{y\in\mathcal{X}:d(x,y)<\rho_{x}}\lambda_{y}$.

We now give the main result of this section.

######  Theorem 25.

Consider an instance of the $f$-MPMD problem such that
$\mathbb{E}[f(X)]<\infty$, where $X\sim{\rm Exp}(\lambda(\mathcal{X}))$ is an
exponential variable of parameter
$\lambda(\mathcal{X}):=\sum_{x\in\mathcal{X}}\lambda_{x}$. Then, both the
Greedy and Radius algorithms achieve ratio-of-expectations of $O(K_{f})$,
where

$K_{f}:=\max_{\mu>0}\left\\{\dfrac{\mathbb{E}[f(X)]}{\mathbb{E}[\min(f(X^{\prime}),\mathbb{E}[f(X)])]},\text{
where }X\sim{\rm Exp}(\mu)\text{ and }X^{\prime}\sim{\rm Exp}(2\mu)\right\\}.$

The condition $\mathbb{E}[f(X)]<\infty$ means that the expected delay cost
corresponding to the duration between any two consecutive requests in the
random sequence is finite. Without this assumption, even the expected cost of
the optimal offline matching, over all random sequence of length $m=2$, is
infinite. Notice that under this assumption, we have that the radius (as
defined in Definition 24) for each point, is finite.

The full proof of Theorem 25 is presented in Appendix B and follows the same
framework as for the linear case. The upper bounds on the expected costs of
Greedy and Radius are the same as the upper bounds in Lemmas 11 and 12. The
factor $O(K_{f})$ in the ratio-of-expectations comes from the analysis of the
expected cost of the optimal offline solution. Essentially, we show that in a
random sequence $\sigma$, for any request located at point $x$, its
(generalised) minimum total cost in $\sigma$ is in expectation
$\rho_{x}/K_{f}$.444The original definition for linear delays is given just
before Claim 14. Here, we need to adapt this notion to the new delay cost
function $f$.

There are several natural functions $f$ for which we can give an explicit
value of $K_{f}$. For example, in the linear case, that is when $f(t)=t$, it
follows directly from Claim 16 that $K_{f}=2/(1-e^{-2})$. More generally, in
the case when $f(t)=t^{\alpha}$, for some positive constant $\alpha\geq 0$,
which has been studied in [24], we show in Appendix B that

######  Proposition 26.

$K_{f}=e^{O({\alpha})}$ when $f(t)=t^{\alpha}$, with $\alpha\geq 0$.

Notice that for any polynomial function $f$ (so in particular for all
functions $t\mapsto t^{\alpha}$), and any exponential variable $X$, we have
$\mathbb{E}[f(X)]<\infty$. Thus, we obtain the following corollary.

######  Corollary 27.

Both the Greedy and the Radius algorithms achieve a ratios-of-expectations of
$e^{O({\alpha})}$ for the $t^{\alpha}$-MPMD problem.

##  8 Paying penalties to clear pending requests

In this section, we consider a variant of MPMD called MPMDfp [18], where it is
allowed to clear any request by paying a fixed penalty $p>0$. For this
problem, we propose the following algorithm ${\rm ALG}$, that works similarly
to Radius, obtaining a constant ratio-of-expectations.

Given the metric space ($\mathcal{X},d$), define
$\mathcal{X}^{(1)}=\\{x\in\mathcal{X}:\rho_{x}<p\\}$ and
$\mathcal{X}^{(2)}=\\{x\in\mathcal{X}:\rho_{x}\geq p\\}$ (where $\rho_{x}$ is
the radius of point $x\in\mathcal{X}$ as defined in Definition 9). Suppose
that at time $t$, a new request $r$ arrives. Then, our algorithm performs the
following actions depending on whether $\ell(r)\in\mathcal{X}^{(2)}$ or
$\ell(r)\in\mathcal{X}^{(1)}$:

  * -

Suppose $\ell(r)\in\mathcal{X}^{(2)}$. If there exists a pending request
$r^{\prime}$ located at point $y\in\mathcal{X}^{(1)}$ and
$x\in\overline{B}(y,\rho_{y})$, then match $r$ with $r^{\prime}$. Otherwise,
clear $r$.

  * -

Suppose $\ell(r)\in\mathcal{X}^{(1)}$. Apply the Radius algorithm to match
this request.

Notice that there possibly exists an odd number of late requests (due to
clearing an odd number of requests arriving at points $\mathcal{X}^{(2)}$). In
that case, ${\rm ALG}$ has to clear the last request $r_{m}$ even when
$\ell(r_{m})\in\mathcal{X}^{(1)}$.

######  Theorem 28.

For MPMDfp in the Poisson arrival model, ${\rm ALG}$ achieves a ratio-of-
expectations of $8/(1-e^{-2})$.

The full proof of this theorem is presented in Appendix C, and follows the
same framework as sketched in Section 3. On the one hand, we lower bound
$\mathbb{E}_{\sigma}^{m}[{\rm OPT}(\sigma)]$ by

$m\cdot\frac{1-e^{-2}}{4}\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\min\\{\rho_{x},p\\};$

on the other hand, we upper bound the expected cost produced by ${\rm ALG}$ by

$\left(2m\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\min\\{\rho_{x},p\\}\right)+\frac{1}{2}\cdot|\mathcal{X}|\cdot
d_{max}.$

#### Remark.

In [18], Emek et al. showed a reduction from MPMD to MPMDfp in the case where
$\smash{p<2\cdot d_{\max}}$. They argue that any online algorithm for the
instance of MPMD obtained by this reduction can be turned into an algorithm
for the original instance of MPMDfp, while only loosing a factor 2 in the
competitive ratio.

##  9 Conclusion

In this paper, we considered the online problem of Min-cost Perfect Matching
with Delays (MPMD) with additional stochastic assumption on the sequence of
the input requests. In the case where the requests follow a Poisson arrival
process, we presented two simple deterministic online algorithms with constant
ratios-of-expectations. In particular, we observed that the cost of the
optimal offline solution is proportional to the number of requests in the
sequence, and gave a tight (up to a constant factor independent from the
instance) estimation of the constant of proportionality.

In the following text, we briefly discuss some potential future directions.

###  9.1 The bipartite case in the Poisson arrival model

Previously, the bipartite version of MPMD (i.e., MBPMD) has been considered in
the adversarial model [1] where each request has a colour, either red or blue,
and only requests of different colours can be matched into a pair555For an
application, imagine that the red requests come from customers and the blue
ones represent the suppliers.. In an equivalent definition, given the metric
space $\mathcal{M}=(\mathcal{X},d)$, the points of $\mathcal{X}$ are
partitioned into two subsets $A$ and $B$, such that the requests arriving at
points $A$ can only be matched with requests from points $B$. Ashlagi et al.
[1] proposed two O($\log n$)-competitive randomised online algorithms for this
problem. Besides, they established a lower bound of $\Omega(\sqrt{\log
n/\log\log n})$ on the competitive ratio of any online algorithm. Note that
the MBPMD problem can be seen as a special case of the _non-metric_ perfect
matching problem with delays, where the connection cost function
$d:\mathcal{X}\times\mathcal{X}\rightarrow\mathcal{R}_{+}\cup\\{\infty\\}$ can
have infinite values and is no longer assumed to satisfy the triangle
inequality.

A natural direction would be to explore MBPMD in the Poisson arrival model.
Unfortunately, the following observation establishes an initial difficulty:
the expected cost of the offline optimal algorithm, on random sequence of
length $m$, cannot be upper bounded by $O(m)$.

######  Lemma 29.

Let $\mathcal{X}=\\{a,b\\}$, and assume that the connection cost $d$ satisfies
$d(a,a)=d(b,b)=\infty$ and $d(a,b)=d(b,a)=0$. In the Poisson arrival model,
the red (resp. blue) requests arrive at point $a$ (resp. $b$) with a Poisson
arrival rate $\lambda_{a}=1/2$ (resp. $\lambda_{b}=1/2$). Let $\sigma$ be a
random request sequence of length $m$. Consider the algorithm ${\rm ALG}$ that
matches any two pending requests from $a$ and $b$ greedily. Then,
$\mathbb{E}_{\sigma}^{m}[{\rm ALG}(\sigma)]=\Omega(m\sqrt{m})$.

###### Proof.

First, notice that ${\rm ALG}$ is the optimal algorithm in both online and
offline settings. Given any $i\in\\{1,\dots,m\\}$, let $P_{i}$ denote the
(random) number of requests still pending right after the arrival of $i$-th
request. Let $W_{i}$ denote the time duration between the arrival times of
$i$-th and ($i+1$)-th requests. Since $\lambda_{a}=\lambda_{b}=1/2$, we have
$W_{i}\sim{\rm Exp}(1)$. The total cost of ${\rm ALG}$, which corresponds to
its total delay cost, is

${\rm ALG}(\sigma)=\sum_{i=1}^{m-1}P_{i}\cdot W_{i}.$

Since $W_{i}$ is independent from $P_{i}$ according to Definition 7, for any
$i\in\\{1,\dots,m\\}$, we have

$\mathbb{E}_{\sigma}^{m}[{\rm
ALG}(\sigma)]=\sum_{i=1}^{m-1}\mathbb{E}_{\sigma}^{m}[P_{i}]\cdot\mathbb{E}_{\sigma}^{m}[W_{i}]=\sum_{i=1}^{m-1}\mathbb{E}_{\sigma}^{m}[P_{i}].$

Note that $\\{P_{i}\\}_{i}$ is the translation distance of a (uniform) one-
dimensional random walk. It is known (see e.g. [26]) that:

$\mathbb{E}[P_{i}]\sim\sqrt{\frac{2}{\pi}}\cdot\sqrt{i}.$

This implies that

$\mathbb{E}_{\sigma}^{m}[{\rm
ALG}(\sigma)]=\sum_{i=1}^{m-1}\mathbb{E}_{\sigma}^{m}[P_{i}]=\Omega\left(\sum_{i=1}^{m-1}\sqrt{i}\right)=\Omega(m\sqrt{m}).$

∎

In the bipartite case, since two requests on the same point cannot be matched
together, pending requests on the same point will accumulate over time,
forming queues. In particular, the waiting time of a request depends on the
size of the queue at the time of its arrival. By the previous lemma, we know
that the size of the queues will grow to infinite, and in particular, as time
passes by, the delay cost will become arbitrarily larger than the connection
cost. This suggests that a simple algorithm that matches any two pending
requests, no matter how large their connection cost is, is essentially the
best possible online algorithm for this stochastic version of MBPMD.

###  9.2 $k$-way min-cost perfect matching with delays

Another direction, that was introduced by [25] for the online adversarial
model, would be to consider a generalised $k$-way min-cost perfect matching
with delays ($k$-MPMD) in the stochastic input model, where each pair (a.k.a.,
$k$-tuple) consists of $k$ different requests ($k\geq 2$ is an arbitrary
integer). Note that such $k$-MPMD problem indeed has real applications from
ride-sharing taxi platforms (when a taxi picks up $k$ passengers from
different locations for one ride) and online gaming platforms (when a gaming
session consists of $k$ different players). To attack this version of the MPMD
problem, one should first come out with a suitable notion of “connection cost”
of a $k$-set. This might be for instance measured by the maximum distance
between any two requests of that set, the average distance, the weight of a
minimum spanning tree, etc.

## References

  * [1] I. Ashlagi, Y. Azar, M. Charikar, A. Chiplunkar, O. Geri, H. Kaplan, R. Makhijani, Y. Wang, and R. Wattenhofer, Min-cost bipartite perfect matching with delays, in Proc. APPROX / RANDOM, 2017, pp. 1:1–1:20.
  * [2] Y. Azar, A. Chiplunkar, and H. Kaplan, Polylogarithmic bounds on the competitiveness of min-cost perfect matching with delays, in Proc. SODA, 2017, pp. 1051–1061.
  * [3] Y. Azar, A. Chiplunkar, S. Kutten, and N. Touitou, Set cover with delay–clairvoyance is not required, in Proc. ESA, 2020.
  * [4] Y. Azar, Y. Emek, R. van Stee, and D. Vainstein, The price of clustering in bin-packing with applications to bin-packing with delays, in Proc. SPAA, 2019, pp. 1–10.
  * [5] Y. Azar, A. Ganesh, R. Ge, and D. Panigrahi, Online service with delay, in Proc. STOC, 2017, pp. 551–563.
  * [6] Y. Azar and A. Jacob-Fanani, Deterministic min-cost matching with delays, Theory of Computing Systems, 64 (2020), pp. 572–592.
  * [7] Y. Azar, R. Ren, and D. Vainstein, The min-cost matching with concave delays problem, in Proc. SODA, 2021, pp. 301–320.
  * [8] Y. Azar and N. Touitou, General framework for metric optimization problems with delay or with deadlines, in Proc. FOCS, 2019, pp. 60–71.
  * [9] , Beyond tree embeddings–a deterministic framework for network design with deadlines or delay, in Proc. FOCS, 2020, pp. 1368–1379.
  * [10] M. Bienkowski, M. Böhm, J. Byrka, M. Chrobak, C. Dürr, L. Folwarcznỳ, Ł. Jeż, J. Sgall, K. T. Nguyen, and P. Veselỳ, Online algorithms for multi-level aggregation, in Proc. ESA, 2016.
  * [11] M. Bienkowski, M. Böhm, J. Byrka, and J. Marcinkowski, Online facility location with linear delay, arXiv preprint arXiv:2110.15155, (2021).
  * [12] M. Bienkowski, A. Kraska, H.-H. Liu, and P. Schmidt, A primal-dual online deterministic algorithm for matching with delays, in Proc. WAOA, 2018, pp. 51–68.
  * [13] M. Bienkowski, A. Kraska, and P. Schmidt, A match in time saves nine: Deterministic online matching with delays, in Proc. WAOA, 2017, pp. 132–146.
  * [14] , Online service with delay on a line, in Proc. SIROCCO, 2018, pp. 237–248.
  * [15] N. Buchbinder, M. Feldman, J. Naor, and O. Talmon, O(depth)-competitive algorithm for online multi-level aggregation, in Proc. SODA, 2017, pp. 1235–1244.
  * [16] R. A. Carrasco, K. Pruhs, C. Stein, and J. Verschae, The online set aggregation problem, in Proc. LATIN, 2018, pp. 245–259.
  * [17] R. Chen, J. Khatkar, and S. W. Umboh, Online weighted cardinality joint replenishment problem with delay, in Proc. ICALP, 2022, pp. 40:1–40:18.
  * [18] Y. Emek, S. Kutten, and R. Wattenhofer, Online matching: haste makes waste!, in Proc. STOC, 2016, pp. 333–344.
  * [19] Y. Emek, Y. Shapiro, and Y. Wang, Minimum cost perfect matching with delays for two sources, Theoretical Computer Science, 754 (2019), pp. 122–129.
  * [20] L. Epstein, On bin packing with clustering and bin packing with delays, Discrete Optimization, 41 (2021), p. 100647.
  * [21] N. Garg, A. Gupta, S. Leonardi, and P. Sankowski, Stochastic analyses for online combinatorial optimization problems, in Proc. SODA, 2008, pp. 942–951.
  * [22] A. Gupta, A. Kumar, and D. Panigrahi, Caching with time windows, in Proc. STOC, 2020, pp. 1125–1138.
  * [23] R. M. Karp, U. V. Vazirani, and V. V. Vazirani, An optimal algorithm for on-line bipartite matching, in Proc. STOC, 1990, pp. 352–358.
  * [24] X. Liu, Z. Pan, Y. Wang, and R. Wattenhofer, Impatient online matching, in Proc. ISAAC, vol. 123, 2018, pp. 62:1–62:12.
  * [25] D. Melnyk, Y. Wang, and R. Wattenhofer, Online k-way matching with delays and the h-metric, arXiv preprint arXiv:2109.06640, (2021).
  * [26] R. E. K. Mosteller, F.; Rourke and G. B. Thomas, Probability and Statistics, MA: Addison-Wesley, 1961.
  * [27] M. A. Pinsky and S. Karlin, 5 - poisson processes, in An Introduction to Stochastic Modeling, M. A. Pinsky and S. Karlin, eds., Academic Press, Boston, fourth edition ed., 2011, pp. 223–276.
  * [28] N. Touitou, Nearly-tight lower bounds for set cover and network design with deadlines/delay, in Proc. ISAAC, 2021, pp. 53:1–53:16.

##  Appendix A Elementary proof of Proposition 15

In this section, we present a proof of Proposition 15 that is more elementary
than the one included in the main part of this paper. First, let us restate
this proposition.

See 15

It is known that we can look at a Poisson process as the limit of a Bernoulli
process. In our case, it means that we can proceed in two steps. First, we
have to divide the timeline $[0,\infty)$ into tiny sub-intervals of length
$\delta$. Then, for each of them, toss a coin with success probability
$\lambda(\mathcal{X})\delta$ to decide whether it contains a request arrival.
Finally, in our process, we also have to draw the locations. By Definition 7,
we do it independently for each request with the probability of it appearing
at point $x$ equal to $\lambda_{x}/\lambda(\mathcal{X})$ for each
$x\in\mathcal{X}$.

Now, w.l.o.g., let us assume that $i=1$ and $t(r_{1})=0$, as we only look at
the future requests here. Let $W$ denote the waiting time for the first
request arriving after $r_{1}$ at any point of $\mathcal{S}$. Our aim is to
find the tail distribution $\bar{F}_{W}(t)$ of $W$. For this purpose, we
notice that at any given time $t>0$, it holds that a request can arrive
between $t$ and $t+\delta$ with probability $\lambda(\mathcal{X})\cdot\delta$.
Moreover, the chances of its location belonging to $\mathcal{S}$ are equal to
$\lambda(\mathcal{S})/\lambda(\mathcal{X})$. Thus, we can write that

$\bar{F}_{W}(t+\delta)=\bar{F}_{W}(t)-\bar{F}_{W}(t)\cdot\lambda(\mathcal{X})\cdot\delta\cdot\dfrac{\lambda(\mathcal{S})}{\lambda(\mathcal{X})}$

which is equivalent to

$\bar{F}_{W}(t+\delta)-\bar{F}_{W}(t)=-\bar{F}_{W}(t)\cdot\delta\cdot\lambda(\mathcal{S}).$

After dividing both sides by $\delta$ and taking the limit $\delta\to 0$, we
obtain

$\bar{F}_{W}^{\prime}(t)=-\lambda(\mathcal{S})\cdot\bar{F}_{W}(t).$

Together with condition $\bar{F}_{W}(0)=1$, it implies that
$\bar{F}_{W}(t)=e^{-\lambda(\mathcal{S})t}$. Thus, the cumulative distribution
function of $W$ equals $1-e^{-\lambda(\mathcal{S})t}$, which means that $W$
has an exponential distribution with parameter $\lambda(\mathcal{S})$.

##  Appendix B Missing proofs in Section 7

We show that w.l.o.g., we can assume that the delay cost function $f$
satisfies $f(0)=0$.

######  Claim 30.

Let $f$ be any positive and non-decreasing function, and define a new function
$\hat{f}$ with $\hat{f}(t)=f(t)-f(0)$. Suppose that there exists a
$C$-competitive algorithm $\widehat{{\rm ALG}}$ for $\hat{f}$-MPMD, for some
constant $C>0$. Then, $\widehat{{\rm ALG}}$ is also $C$-competitive for
$f$-MPMD.

###### Proof.

For any input sequence $\sigma$ of length $m$, we have ${\rm
ALG}(\sigma)=\widehat{{\rm ALG}}(\sigma)+m\cdot f(0)$, where ${\rm
ALG}(\sigma)$ and $\widehat{{\rm ALG}}(\sigma)$ respectively denote the cost
of the algorithm with delay cost functions $f$ and $\hat{f}$. Similarly, it is
easy to see that ${\rm OPT}(\sigma)=\widehat{{\rm OPT}}(\sigma)+m\cdot f(0)$,
where ${\rm OPT}(\sigma)$ and $\widehat{{\rm OPT}}(\sigma)$ denote the total
cost of the optimal offline solutions, with respective delay cost functions
$f$ and $\hat{f}$. In particular,

$\frac{{\rm ALG}(\sigma)}{{\rm OPT}(\sigma)}=\frac{\widehat{{\rm
ALG}}(\sigma)+m\cdot f(0)}{\widehat{{\rm OPT}}(\sigma)+m\cdot
f(0)}\leq\frac{\widehat{{\rm ALG}}(\sigma)}{\widehat{{\rm OPT}}(\sigma)}$

which proves the claim. ∎

###  B.1 Proof of Theorem 25

The proof is similar as the proof of Theorems 1 and 2. We first prove the
following upper bounds on the expected cost of the solutions of Radius and
Greedy:

$\mathbb{E}_{\sigma}^{m}[{\rm
Radius}(\sigma)]\leq\left(2m\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\rho_{x}\right)+\frac{1}{2}\cdot|\mathcal{X}|\cdot
d_{\max},$ (6) $\mathbb{E}_{\sigma}^{m}[{\rm
Greedy}(\sigma)]\leq\left(4m\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\rho_{x}\right)+2|\mathcal{X}|\cdot\left(d_{\max}+\frac{1}{\lambda(\mathcal{X})}\right),$
(7)

where the radii $\\{\rho_{x}\\}_{x\in\mathcal{X}}$ are defined in Definition
24. On the other hand, we establish the following lower bound on the expected
cost of the optimal offline solution:

$\mathbb{E}_{\sigma}^{m}[{\rm
OPT}(\sigma)]\geq\frac{m}{2K_{f}}\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\rho_{x}.$
(8)

The proofs of inequalities (6) and (7) are almost identical as the proofs of
Lemmas 12 and 11. Here we only show how to adapt the framework developed in
Section 6 to obtain inequality (6).

We use the same definition of nice and late requests. In particular, Claim 21
still holds, i.e., the connection cost induced by late edges is at most
$|\mathcal{X}|\cdot d_{\max}/2$. Since the algorithm is the same, Claim 22
still holds: for any sequence $\sigma$, the connection cost induced by all
nice edges is at most $\sum_{r\in\sigma}\rho_{\ell(r)}$. To bound the delay
cost of nice and late requests, we define $Y_{r}$, for each request
$r\in\sigma$ exactly as in Section 6:

$Y_{r}:=\min\left\\{t(r_{m})-t(r),\min_{r^{\prime}\in\sigma}\left\\{t(r^{\prime})-t(r)\mid
t(r^{\prime})>t(r)\text{ and
}d(\ell(r^{\prime}),\ell(r))\leq\rho_{\ell(r)}\right\\}\right\\}.$

Again, Claim 23 holds: each request is delayed by the Radius algorithm for a
duration at most $Y_{r}$. The only slight difference with the proof from
Section 6 comes when we establish an upper bound on the expected total delay
cost of the solution.

Similarly, for each point $x\in\mathcal{X}$, let
$\overline{W}(x,\rho_{x})\sim{\rm Exp}(\lambda(\overline{B}(x,\rho_{x})))$ be
an exponential variable of parameter
$\lambda(\overline{B}(x,\rho_{x}))=\sum_{y\in\overline{B}(x,\rho_{x})}\lambda_{y}$.
Let us consider a random sequence $\sigma=(r_{1},\dots,r_{m})$ ordered with
increasing arrival times, and let us assume that the $i$-th request $r_{i}$ is
located at point $x$. By Proposition 15, the (random) variable $Y_{r}$,
follows the same distribution as
$\min\\{\overline{W}(x,\rho_{x}),t(r_{m})-t(r_{i})\\}$. Using the general
definition of radius (Definition 24), instead of Observation 10, we obtain:

$\displaystyle\mathbb{E}_{\sigma}^{m}\left[{\rm DC}\right]$
$\displaystyle\leq\mathbb{E}_{\sigma}^{m}\left[\sum_{i=1}^{m}f(Y_{r_{i}})\right]$
$\displaystyle=\sum_{i=1}^{m}\sum_{x\in\mathcal{X}}\mathbb{P}(\ell(r_{i})=x)\cdot\mathbb{E}_{\sigma}^{m}\left[f(Y_{r_{i}})\mid\ell(r_{i})=x\right]$
$\displaystyle=\sum_{i=1}^{m}\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\mathbb{E}\left[f(\min\\{\overline{W}(x,\rho_{x}),t(r_{m})-t(r_{i}))\\}\right]$
$\displaystyle\leq\sum_{i=1}^{m}\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\mathbb{E}\left[f(\overline{W}(x,\rho_{x}))\right]$
($f$ is non-decreasing)
$\displaystyle\leq\sum_{i=1}^{m}\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\rho_{x}$
(Definition 24)
$\displaystyle=m\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\rho_{x},$

which complete the proof of inequality (6).

#### Proof of inequality (8).

The proof is similar as the proof of Lemma 13. The main difference is that
instead of using Claim 16, we use the definition of $K_{f}$.

Similarly, given a request sequence $\sigma$ and any request $r\in\sigma$, we
define the _minimum total cost of $r$ in $\sigma$_ as

$c(\sigma,r):=\min_{r^{\prime}\in\sigma,r^{\prime}\neq
r}\left\\{d(\ell(r),\ell(r^{\prime}))+f(t(r)-t(r^{\prime}))\right\\}.$

With the same proof as Claim 14, we have ${\rm
OPT}(\sigma)\geq\frac{1}{2}\sum_{r\in\sigma}c(\sigma,r)$.

######  Claim 31.

Given any sequence $\sigma$, we order the requests in
$\sigma=(r_{1},\dots,r_{m})$ according to their arrival times. Then, for any
point $x\in\mathcal{X}$ and any index $i\in\\{1,\dots,m\\}$, the expected
minimum cost of the $i$-th request $r_{i}$ in a random sequence $\sigma$,
assuming that $r_{i}$ is located at point $x$, is

$\mathbb{E}_{\sigma}^{m}[c(\sigma,r_{i})\mid\ell(r_{i})=x]\geq\frac{\rho_{x}}{K_{f}}.$

###### Proof.

The proof is similar as the proof of Claim 17. In particular, using the same
argumentation, it is enough to establish the bound of Claim 31 for extended
random request sequences $\overline{\sigma}$. Exactly as before, we can prove
that

$\mathbb{E}_{\sigma}^{m}[c(\sigma,r_{i})\mid\ell(r_{i})=x]\geq\mathbb{E}\Big{[}\min\big{\\{}f(\min\\{W^{+},W^{-}\\}),\rho_{x}\big{\\}}\Big{]},$

where $W^{+}$ and $W^{-}$ are two independent random exponential variables of
parameter $\lambda(B^{\circ}(x,\rho_{x}))$. In particular, the random variable
$W=\min\\{W^{+},W^{-}\\}$ is an exponential variable of parameter
$2\lambda(B^{\circ}(x,\rho_{x}))$. As we observed after Definition 24, we know
that $\mathbb{E}[f(W^{+})]\geq\rho_{x}$. Let us define $X$ and $X^{\prime}$
two independent exponential variables of parameters $1/\rho_{x}$ and
$2/\rho_{x}$ respectively. We have $\rho_{x}=\mathbb{E}[f(X)]$. Using the
definition of $K_{f}$, we have:

$\displaystyle\mathbb{E}_{\sigma}^{m}[c(\sigma,r_{i})\mid\ell(r_{i})=x]$
$\displaystyle\geq\mathbb{E}[\min\\{f(W),\rho_{x}\\}]\geq\mathbb{E}\big{[}\min\\{f(X^{\prime}),\rho_{x}\\}\big{]}$
$\displaystyle=\frac{\mathbb{E}\Big{[}\min\big{\\{}f(X^{\prime}),\mathbb{E}[f(X)]\big{\\}}\Big{]}}{\mathbb{E}[f(X)]}\cdot\mathbb{E}[f(X)]\geq\frac{\rho_{x}}{K_{f}},$

where the second inequality holds since ${2}/{\rho_{x}}\geq
2\lambda(B^{\circ}(x,\rho_{x})))$ and $t\mapsto\min\\{f(t),\rho_{x}\\}$ is
non-decreasing. This concludes the proof of Claim 31. We obtain inequality (8)
from this claim, similarly as in the proof of Lemma 13. This concludes the
proof of Theorem 25. ∎

###  B.2 Proof of Proposition 26

In this section, we prove that $K_{f}=e^{O({\alpha})}$ when $f(t)=t^{\alpha}$
and $\alpha>0$. Let $\mu>0$ and define $X$ and $X^{\prime}$ two independent
exponential variables of parameters $\mu$ and $2\mu$ respectively. We have

$\mathbb{E}[f(X)]=\int_{0}^{\infty}t^{\alpha}\mu e^{-\mu
t}dt=\frac{\Gamma(\alpha+1)}{\mu^{\alpha}}$

where $\Gamma(\cdot)$ is the Gamma function. We obtain the follows expression.

$\displaystyle\mathbb{E}[\min\\{f(X^{\prime}),\mathbb{E}[f(X)]\\}]$
$\displaystyle=\int_{0}^{\sqrt[\alpha]{\mathbb{E}[f(X)]}}t^{\alpha}\cdot 2\mu
e^{-2\mu
t}dt+{\mathbb{E}[f(X)]}\cdot\mathbb{P}\left(f(X^{\prime})>\mathbb{E}[f(X)]\right)$

One can express the first term using the incomplete Gamma function. However
for simplicity, we only lower this term by $0$, and we obtain

$\displaystyle\frac{\mathbb{E}[\min\\{f(X^{\prime}),\mathbb{E}[f(X)]\\}]}{{\mathbb{E}[f(X)]}}$
$\displaystyle\geq\mathbb{P}\left(f(X^{\prime})>\mathbb{E}[f(X)]\right)=\mathbb{P}\left(X^{\prime}>f^{-1}\left(\mathbb{E}[f(X)]\right)\right)$
$\displaystyle=\mathbb{P}\left(X^{\prime}>\sqrt[\alpha]{\frac{\Gamma(\alpha+1)}{\mu^{\alpha}}}\right)=\text{exp}\left(-2\mu\sqrt[\alpha]{\frac{\Gamma(\alpha+1)}{\mu^{\alpha}}}\right).$

Thanks to Stirling formula, when $\alpha$ goes to infinity, we have

$\sqrt[\alpha]{\Gamma(\alpha+1)}\sim\frac{\alpha}{e}\cdot(1+o(1)).$

This implies that

$K_{f}\geq\frac{\mathbb{E}[\min\\{f(X^{\prime}),\mathbb{E}[f(X)]\\}]}{{\mathbb{E}[f(X)]}}\geq\mathbb{P}\left(f(X^{\prime})>\mathbb{E}[f(X)]\right)\geq
e^{2\alpha(1+o(1))/e}=e^{O(\alpha)},$

which concludes the proof of the proposition.

##  Appendix C Missing proofs in Section 8

#### Lower bounding $\mathbb{E}_{\sigma}^{m}[{\rm OPT}(\sigma)]$.

Given any input sequence $\sigma$ and any request $r\in\sigma$, define

$c^{\prime}(\sigma,r)=\min\\{c(\sigma,r),p\\},$

where $c(\sigma,r):=\min_{r^{\prime}\in\sigma,r^{\prime}\neq
r}\left\\{d(\ell(r),\ell(r^{\prime}))+|t(r)-t(r^{\prime})|\right\\}$ is the
minimum total cost of $r$, defined in the proof of Lemma 13. Note that if $r$
is cleared in ${\rm OPT}(\sigma)$, then a total cost of $p\geq
c^{\prime}(\sigma,r)$ is incurred for dealing with such request; otherwise,
$r$ is matched with another request $r^{\prime}$ in ${\rm OPT}(\sigma)$, and
hence a cost of $d(\ell(r),\ell(r^{\prime}))+|t(r)-t(r^{\prime})|\geq
c(\sigma,r)\geq c^{\prime}(\sigma,r)$ is incurred for producing such pair.
Therefore, we have ${\rm
OPT}(\sigma)\geq\frac{1}{2}\sum_{r\in\sigma}c^{\prime}(\sigma,r)$ for any
input sequence $\sigma$. Similar to the proof of Lemma 13, now we only need to
prove

$\mathbb{E}_{\sigma}^{m}[c^{\prime}(\sigma,r)]\geq\frac{1-e^{-2}}{2}\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\min\\{\rho_{x},p\\}.$

Thanks to the definitions of extended sequence $\overline{\sigma}$, $W^{-}$
and $W^{+}$ introduced in the proof of Claim 17, we further have

$c^{\prime}(\overline{\sigma},r_{0})\geq\min\Big{\\{}\min\\{W^{-},W^{+}\\},\rho_{x},p\Big{\\}}=\min\Big{\\{}\min\\{W^{-},W^{+}\\},\min\\{\rho_{x},p\\}\Big{\\}}.$

Note that given any metrical point $x\in\mathcal{X}^{(1)}$, i.e., $\rho_{x}<p$
and hence $\min\\{\rho_{x},p\\}=\rho_{x}$, by the definition of radius
(Definition 9),

$\frac{1}{\lambda(B^{\circ}(x,\rho_{x}))}\geq\rho_{x},\text{ i.e.,
}\lambda(B^{\circ}(x,\rho_{x}))\cdot\rho_{x}\leq 1;$

given any metrical point $x\in\mathcal{X}^{(2)}$, i.e., $\rho_{x}\geq p$ and
hence $\min\\{\rho_{x},p\\}=p$,

$\frac{1}{\lambda(B^{\circ}(x,\rho_{x}))}\geq\rho_{x}\geq p,\text{ i.e.,
}\lambda(B^{\circ}(x,\rho_{x}))\cdot p\leq 1.$

In summary, for any metrical point $x\in X$, we have

$A:=\lambda(B^{\circ}(x,\rho_{x}))\cdot\min\\{\rho_{x},p\\}\leq 1.$

By Claim 16, with $a=\min\\{\rho_{x},p\\}$,
$\mu=2\lambda(B^{\circ}(x,\rho_{x}))$, we thus have

$\mathbb{E}_{\overline{\sigma}}[c^{\prime}(\overline{\sigma},r_{0})\mid\ell(r_{0})=x]\geq\mathbb{E}_{\overline{\sigma}}\Big{[}\min\big{\\{}\min\\{W^{-},W^{+}\\},\min\\{\rho_{x},p\\}\big{\\}}\Big{]}=\frac{1-e^{-2A}}{2A}\cdot\min\\{\rho_{x},p\\}.$

Recall that $x\mapsto\frac{1-e^{-x}}{x}$ is a strictly decreasing function of
$x>0$ and $A\leq 1$. We have $\frac{1-e^{-2A}}{2A}\geq\frac{1-e^{-2}}{2}$ and
hence

$\mathbb{E}_{\overline{\sigma}}[c^{\prime}(\overline{\sigma},r_{0})\mid\ell(r_{0})=x]\geq\frac{1-e^{-2}}{2}\cdot\min\\{\rho_{x},p\\}.$

Thanks to Proposition 6, we immediately have

$\mathbb{E}_{\overline{\sigma}}[c^{\prime}(\overline{\sigma},r_{0})]\geq\frac{1-e^{-2}}{2}\sum_{x\in\mathcal{X}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\min\\{\rho_{x},p\\}.$

#### Upper bounding $\mathbb{E}_{\sigma}^{m}[{\rm ALG}(\sigma)]$.

Given any input sequence $\sigma$, we classify the requests into two groups
according to their locations

$\sigma^{(1)}=\\{r\in\sigma:\ell(r)\in\mathcal{X}^{(1)}\\}\text{ and
}\sigma^{(2)}=\\{r\in\sigma:\ell(r)\in\mathcal{X}^{(2)}\\}.$

By definition of our algorithm, we rewrite ${\rm ALG}(\sigma)={\rm
ALG}_{m}(\sigma)+{\rm ALG}_{p}(\sigma)$, where ${\rm ALG}_{m}(\sigma)$ denotes
the total connection + delay cost, and ${\rm ALG}_{p}(\sigma)$ denotes the
total penalty cost.

We first upper bound ${\rm ALG}_{p}(\sigma)$. Note that the number of requests
being cleared is at most $2|\sigma^{(2)}|$. This is because, if an odd number
of requests from $\sigma^{(2)}$ is cleared, then there exists one late request
from $\sigma^{(1)}$ which is also cleared (i.e., the number of requests being
cleared is $|\sigma^{(2)}|+1\leq 2|\sigma^{(2)}|$); otherwise, all the cleared
requests are from $\sigma^{(2)}$. Since each request in $\sigma^{(2)}$ has its
location’s radius at least $p$, we have

${\rm ALG}_{p}(\sigma)\leq 2|\sigma^{(2)}|\cdot p\leq
2\sum_{r\in\sigma^{(2)}}\min\\{\rho_{\ell(r)},p\\}.$

Thanks to Proposition 6, we have

$\displaystyle\mathbb{E}_{\sigma}^{m}[{\rm ALG}_{p}(\sigma)]\leq
2m\sum_{x\in\mathcal{X}^{(2)}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\min\\{\rho_{\ell(r)},p\\},$
(9)

since each of the $m$ requests has a probability of
$\sum_{x\in\mathcal{X}^{(2)}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}$ to
appear in $\mathcal{X}^{(2)}$ (i.e., in $\sigma^{(2)}$).

Next, we upper bound ${\rm ALG}_{m}(\sigma)$. By definition, when a request
$r\in\sigma^{(2)}$ arrives, either it is matched with a pending request
$r^{\prime}\in\sigma^{(1)}$ or it is cleared immediately. This means no delay
cost is incurred for $\sigma^{(2)}$. Besides, if $r\in\sigma^{(2)}$ is matched
with $r^{\prime}\in\sigma^{(1)}$ into a pair, we know that
$\ell(r)\in\overline{B}(\ell(r^{\prime}),\rho_{\ell(r^{\prime})})$ (i.e., the
connection cost of this pair is bounded by $\rho_{\ell(r^{\prime})}$) and
$r^{\prime}$ is a nice request. As a result, ${\rm ALG}_{m}(\sigma)$ is
produced from $\sigma^{(1)}$. Note that requests $\sigma^{(1)}$ are matched by
applying our Radius algorithm. Same as the proofs of Claim 21, Claim 22 and
Claim 23, we have

  * -

the connection costs for matching all the late requests in $\sigma^{(1)}$ is
bounded by $\frac{1}{2}\cdot|\mathcal{X}|\cdot d_{\max}$;

  * -

the connection cost for matching all the nice requests is bounded by
$\sum_{r\in\sigma^{(1)}}\rho_{\ell(r)}$;

  * -

each request $r\in\sigma^{(1)}$ is delayed for a duration at most $Y_{r}$ (see
$Y_{r}$’s definition above Claim 23).

As a result, thanks to the proof of Lemma 12, here we have

$\displaystyle\mathbb{E}_{\sigma}^{m}[{\rm
ALG}_{m}(\sigma)]\leq\left(2m\sum_{x\in\mathcal{X}^{(1)}}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\rho_{x}\right)+\frac{1}{2}\cdot|\mathcal{X}|\cdot
d_{\max}.$ (10)

By combining inequalities (9) with (10) together, we have

$\displaystyle\mathbb{E}_{\sigma}^{m}[{\rm ALG}(\sigma)]$ $\displaystyle=$
$\displaystyle\mathbb{E}_{\sigma}^{m}[{\rm
ALG}_{m}(\sigma)]+\mathbb{E}_{\sigma}^{m}[{\rm ALG}_{p}(\sigma)]$
$\displaystyle\leq$ $\displaystyle\left(2m\sum_{x\in
X}\frac{\lambda_{x}}{\lambda(\mathcal{X})}\cdot\min\\{\rho_{x},p\\}\right)+\frac{1}{2}\cdot|\mathcal{X}|\cdot
d_{\max},$

which concludes the proof.