A Nearly Optimal Deterministic Algorithm for Online Transportation Problem

First, we will explain how to reduce the task of designing an $O(m)$-competitive algorithm for general instances of $\mathrm{OTR}$ to the task of designing an algorithm for more specific instances. To this end, let us begin by defining two special cases of $\mathrm{OMM}$ and introducing the concept of T-strong competitive ratio, which serves as a stricter performance measure for algorithms compared to the standard competitive ratio.

The first special case of $\mathrm{OMM}$ is $\mathrm{OMM}$ where each request is placed on the same position as a server (denoted by ${\mathrm{OMM}}_S$) and the second one is a further special case of ${\mathrm{OMM}}_S$ called online matching on a power-of-two tree metric (denoted by ${\mathrm{OMT}}_S^2$). In this problem, a metric space is induced by a weighted tree $T=(V(T),E(T))$ in which the weight of each edge is a non-negative integer power of two, and the set of server sites coincides with the set $V(T)$ of vertices. Let ${\mathrm{OMM}}_S(k)$ denote ${\mathrm{OMM}}_S$ with $k$ servers and ${\mathrm{OMT}}_S^2(T)$ denote ${\mathrm{OMT}}_S^2$ with a metric space $T$. Note that $|V(T)|=|E(T)|+1$ is the number of servers in ${\mathrm{OMT}}_S^2(T)$.

The T-strong competitive ratio is defined for $\mathrm{OTR}$ on a tree metric (the “T” is derived from “tree”). While the standard competitive ratio measures both the cost of the algorithm and the cost of the optimal offline algorithm in terms of the sum of the edge weights along the path between requests and servers (commonly referred to as the “path distance”), the T-strong competitive ratio measures the algorithm’s cost using the path distance, whereas the cost of the optimal offline algorithm is measured using the weight of the heaviest edge on the path between the requests and servers (referred to as the “max-weight distance”). In other words, we say that an algorithm is T-strongly $\alpha$-competitive if, for any instance of $\mathrm{OTR}$ on a tree metric, the cost incurred by the algorithm, measured by the path distance, is at most $\alpha$ times the optimal offline cost measured by the max-weight distance. Since the max-weight distance is shorter than the path distance, the T-strong competitive ratio is greater than the standard competitive ratio in general.

In this paper, we demonstrate that if a greedy-like algorithm that only uses the positions of a current request and current available server sites (referred to as MPFS [9]²²2 MPFS is a class of algorithms that generalize the greedy algorithm (see Definition 6 for details). ) is designed to be T-strongly $O(k)$-competitive for ${\mathrm{OMT}}_S^2$ with $k$ servers, it can be transformed into an $O(m)$-competitive algorithm for $\mathrm{OTR}(k,m)$ (Theorem 9). The proof is completed by establishing the following three claims:

1. (1)

   If there exists a T-strongly $O(k)$-competitive algorithm for ${\mathrm{OMT}}_S^2$ with $k$ servers, then there exists an $O(k)$-competitive algorithm for ${\mathrm{OMM}}_S(k)$.

2. (2)

   If there exists an $O(k)$-competitive algorithm for ${\mathrm{OMM}}_S(k)$, then there exists an $O(k)$-competitive algorithm for $\mathrm{OMM}(k)$.

3. (3)

   If a certain MPFS algorithm is $O(k)$-competitive for $\mathrm{OMM}(k)$, then that algorithm is $O(m)$-competitive for $\mathrm{OTR}(k,m)$.

Claim (2) was previously proven by Meyerson et al. [16], and Claim (3) was proven by Harada et al. [9]. In this paper, we prove Claim (1). To this end, we begin by noting that it suffices to demonstrate a method for obtaining an $O(k)$-competitive algorithm for ${\mathrm{OMM}}_S(k)$ with a general $k$-point metric space by using a T-strongly $O(k)$-competitive algorithm for ${\mathrm{OMM}}_S(k)$ on a tree metric (where the edge weights are not necessarily powers of two).

Next, we explain how to convert algorithm $𝒜$, which is T-strongly $\alpha$-competitive for a tree metric, into algorithm $ℬ$, which is $\alpha$-competitive for a general $k$-point metric space $ℳ$. $ℬ$ first treats the given metric space as a weighted complete graph, where the weight of each edge corresponds to the distance between its endpoints. $ℬ$ then finds a minimum spanning tree (MST) $T$ of this graph and simulates algorithm $𝒜$ on $T$.

The key fact to prove that $ℬ$ is $\alpha$-competitive for a general metric space $ℳ$ is that the distance between any two points in the original metric space $ℳ$ lies between the max-weight distance and the path distance on the MST $T$. Using this fact, we can verify that $ℬ$ is $\alpha$-competitive as follows: First, the $ℬ$’s cost measured by the distance in $ℳ$ is at most the $𝒜$’s cost measured by the path distance on $T$. Then, by the T-strong competitiveness of $𝒜$, the $𝒜$’s cost measured by the path distance is at most $\alpha$ times the optimal offline cost measured by the max-weight distance. Since the optimal offline cost measured by the max-weight distance is not greater than the optimal offline cost measured by the distance in $ℳ$, it follows that the $ℬ$’s cost is at most $\alpha$ times the optimal offline cost measured by the distance in $ℳ$.

Finally, we briefly explain why the distance in the original metric space $ℳ$ lies between the max-weight distance and the path distance on the MST $T$. By the triangle inequality, the distance in $ℳ$ is at most the path distance. To see that the distance in $ℳ$ is at least the max-weight distance, consider that if the distance in $ℳ$ between two points $u$ and $v$ were smaller than the max-weight distance on $T$, one could create a spanning tree with a smaller weight by adding edge $(u,v)$ to $T$ and removing the heaviest edge on the $u$-$v$ path in $T$. This would contradict $T$ being an MST.

The above discussion reduces the task of designing an $O(m)$-competitive algorithm for $\mathrm{OTR}(k,m)$ to designing a T-strongly $O(k)$-competitive MPFS algorithm for ${\mathrm{OMT}}_S^2$ with $k$ servers.

In the following, we provide an overview of the T-strongly $O(k)$-competitive algorithm for ${\mathrm{OMT}}_S^2(T)$ with $k$ servers, which we refer to as Subtree-Decomposition (SD). Note that in ${\mathrm{OMT}}_S^2$, the set of vertices coincides with the set of servers, meaning that $k=|V(T)|=|E(T)|+1$.

The proposed algorithm is based on a simple depth-first search (DFS) algorithm. The DFS-based algorithm begins by arbitrarily selecting one vertex in $T$ as the root before receiving any requests. When a request arrives at a vertex, the algorithm performs a DFS starting from that vertex, and assigns the request to the first available server it encounters.

Intuitively, one can understand why the T-strong competitive ratio of this DFS-based algorithm is at most $O(k)$ when the given tree $T$ is unweighted (where each edge has unit weight) as follows: The nature of DFS ensures that any edge will be traversed at most twice by the algorithm’s assignments. In instances where there exist edges traversed more than twice, the optimal offline cost also increases in proportion to the number of such edges, resulting in a sufficiently small ratio of the algorithm’s cost to the optimal offline cost³³3Note that this statement is imprecise, as discussed and justified in this paper through the analysis via “hybrid algorithm” [7].. Thus, the algorithm’s cost measured by the path distance is roughly $O(|E(T)|)=O(k)$. On the other hand, for any request sequence where the algorithm incurs a non-zero cost, the optimal offline cost measured by the max-weight distance is at least 1. Therefore, the ratio of the algorithm’s cost measured by the path distance to the optimal offline cost measured by the max-weight distance is $O(k)$.

However, naive application of this algorithm to a weighted tree results in inefficiencies. For instance, if a request occurs at a vertex where the edges connecting it to its children have very large weights, while the edge connecting it to its parent has a very small weight, the algorithm will prioritize assigning the request to a more costly child. To address this inefficiency, SD performs a stepwise DFS, assigning the request at vertex $v$ to the first available server it encounters by prioritizing the exploration of lighter edges. Specifically, SD proceeds as follows:

1. (1)

   Perform a DFS from $v$, restricted to edges with weights no greater than 1.

2. (2)

   If no available server is found in step 1, return to $v$ and perform another DFS, this time restricted to edges with weights no greater than 2.

3. (3)

   In subsequent steps, double the threshold for edge weights and perform a DFS from $v$ until an available server is found.

Below, we provide an intuitive explanation for why SD is T-strongly $O(k)$-competitive for ${\mathrm{OMT}}_S^2(T)$ with $k$ servers. Let $2^n$ be the weight of the heaviest edge used in the optimal offline assignment. In this case, the optimal offline cost measured by the max-weight distance is at least $2^n$. SD is designed to minimize the number of times it traverses heavy edges, and it can be shown that no edge with weight greater than $2^n$ is traversed in SD’s assignment. Furthermore, an edge with weight exactly $2^n$ is traversed at most twice by the nature of DFS. Similarly, edges with weight $2^{n-1}$ are traversed up to two times during the $(n-1)$-th DFS and another two times during the final $n$-th DFS, for a total of four traversals. Extending this reasoning, for each $i=0,\mathrm{\dots },n$, the number of traversals for an edge with weight $2^i$ in SD’s assignment is expected to be at most $2(n-i+1)\le 2^{n-i+1}$. Therefore, the algorithm’s cost measured by the path distance is roughly at most $O(2^i\times 2^{n-i+1}\times |E(T)|)=O(2^n|E(T)|)$, and the ratio to the optimal offline cost measured by the max-weight distance is $O(|E(T)|)=O(k)$.

To begin with, we define the online metric matching (denoted by $\mathrm{OMM}$). An instance of $\mathrm{OMM}$ is represented by a quadruple $I=(X,d,S,\sigma )$, where $X$ is a set of points, $d:X\times X\to {ℝ}_{\ge 0}$ is a distance function on $X$, $S$ is a finite subset of $X$, and $\sigma =r_1\mathrm{\dots }{r}_{|S|}\in X^{|S|}$. An element of $S$ is called a server and the $t$-th entry $r_t$ of $\sigma$ is called the request at time $t$ or $t$-th request.

$X$, $d$ and $S$ are given to an online algorithm in advance, while requests are given one-by-one from $r_1$ to $r_{|S|}$. At each step, an online algorithm $𝒜$ for $\mathrm{OMM}$ maintains “assignment” that is initialized to $\mathrm{\varnothing }$. When a request $r_t$ is revealed, $𝒜$ must assign $r_t$ to one of the available servers irrevocably. If $r_t$ is assigned to the server $s_t$, then the pair $(r_t,s_t)$ is added to the current assignment and the cost $d(r_t,s_t)$ is incurred for this pair. The cost of the assignment is the sum of the costs of all the pairs contained in it. The goal of an online algorithm is to minimize the cost of the final assignment.

We use the following notation on $\mathrm{OMM}$.

1. (1)

   $\mathrm{OMM}(k)$ denotes $\mathrm{OMM}$ with $k$ servers.

2. (2)

   ${\mathrm{OMM}}_S$ denotes $\mathrm{OMM}$ where requests arrive at the position of some server, i.e., $X=S$. We simply write an instance $I$ of ${\mathrm{OMM}}_S$ as $I=(S,d,\sigma )$ instead of $(S,d,S,\sigma )$.

3. (3)

   ${\mathrm{OMM}}_S(k)$ denotes ${\mathrm{OMM}}_S$ with $k$ servers.

Before presenting online metric matching on a power-of-two tree metric, we first introduce the definitions and notations for the two distance functions used for edge-weighted trees. For an edge-weighted tree $T$, we use $d_T$ to denote the path distance on $V(T)$, i.e., for any $u,v\in V(T)$, $d_T(u,v)≔{\sum }_{e\in E(P_T(u,v))}{w}_T(e),$ where $P_T(u,v)$ denotes the unique simple path in $T$ from $u$ to $v$. In this paper, we define another distance $d_T^{\max }$ on $T$ as follows:

We call $d_T^{\max }$ the max-weight distance on $T$. It is easy to verify that $d_T^{\max }$ defines a metric on $V(T)$ when each edge has a positive weight. By the above definition, we can observe the following relationship between the path distance and the max-weight distance.

Then, we introduce a notion of power-of-two weighted tree and define a special case of ${\mathrm{OMM}}_S$ called online matching on a power-of-two tree metric (denoted by ${\mathrm{OMT}}_S^2$).

The online matching on a power-of-two tree metric is a variant of the online metric matching problem where a metric space $(X,d)$ is induced by a power-of-two weighted tree $T$ and a set $S$ of servers is $V(T)$. In other words, an instance of ${\mathrm{OMT}}_S^2$ is an instance $I=(X,d,S,\sigma )$ of $\mathrm{OMM}$ such that $X=S=V(T)$ and $d=d_T$.

For a power-of-two weighted tree $T$, ${\mathrm{OMT}}_S^2(T)$ denotes ${\mathrm{OMT}}_S^2$ where the metric space is induced by $T$. We simply write an instance $I$ of ${\mathrm{OMT}}_S^2(T)$ as $I=(T,\sigma )$ instead of $(V(T),d_T,V(T),\sigma )$ for $\mathrm{OMM}$.

Finally, we define the online transportation problem (denoted by $\mathrm{OTR}$). In this problem, $k$ servers are clustered in specific $m$ $(\le k)$ locations called server sites. The number of servers at a server site is called the capacity of that site. Assume that each site has a capacity of at least 1. An instance of $\mathrm{OTR}$ is represented by a quintuple $(X,d,S,c,\sigma )$. Here, $(X,d)$ represents the metric space, $S$ represents the set of server sites, $c:S\to \mathbb{N}$ represents the capacity of each site, and $\sigma =r_1\mathrm{\dots }{r}_k\in X^k$ represents the request sequence⁴⁴4 For $\mathrm{OTR}$, the number of requests is generally set to be at most $k$. As can be seen from [9, Lemma 2.1], however, the assumption that the number of requests is exactly $k$ has no effect on the competitive analysis. . $\mathrm{OTR}$ is the same as $\mathrm{OMM}$ except that an online algorithm can assign up to $c(s)$ requests to one server site $s$. In other words, $\mathrm{OMM}$ can be viewed as a special case of $\mathrm{OTR}$ where $k=m$ and each site has unit capacity. We use $\mathrm{OTR}(k,m)$ to denote $\mathrm{OTR}$ with $k$ servers and $m$ $(\le k)$ server sites.