An Improved Lower Bound on the Competitive Ratio of Deterministic Online Algorithms for the Multi-agent K-Canadian Traveler Problem

1. Questions

In the online multi-agent $k$-Canadian Traveler Problem $(m$-$k$-$CTP),$ an undirected connected network $G=(V,E)$ with a given source node $O$ and a destination node $D,$ together with non-negative edge costs are given. There are $L \geq 2$ travelers in the network who are initially located at $O$ and can communicate with each other in real time. There are $k\geq L$ non-recoverable blocked edges in the network which are not known to the travelers beforehand. A blocked edge is discovered online only if it is encountered by at least one of the travelers at one of its end-nodes. It is assumed that the network remains connected if the blocked edges are removed from $E.$ The objective of the travelers is to devise an online algorithm such that at least one of them finds a feasible path without blocked edges, from $O$ to $D$ with minimum total cost of the edges travelled. From a network resilience perspective, the $m$-$k$-$CTP$ investigates how reliable the transportation network is against adversarial blocked edges.

The single-agent version of this problem was introduced by Papadimitriou and Yannakakis (1991) and was analyzed with a bounded number of $k$ blocked edges by Westphal (2008). In the past decade, several papers (Shiri and Salman 2020, 2019a, 2017; Zhang, Xu, and Qin 2013) have investigated online algorithms for the $m$-$k$-$CTP$ by means of competitive ratio described in section 2. A lower bound of $2\lfloor \frac{k}{L}\rfloor +1$ on the competitive ratio of deterministic algorithms (Zhang, Xu, and Qin 2013) is the best lower bound found so far for this problem on general networks. However, an optimal deterministic online algorithm which meets this lower bound has not been provided so far. In this work, with the aim of narrowing the gap between the lower bound and worst-case performance of online algorithms, we prove a lower bound on the competitive ratio of deterministic online algorithms for the $m$-$k$-$CTP$ which is tighter than the lower bound of $2\lfloor \frac{k}{L}\rfloor +1$ given in the literature.

2. Methods

In the competitive analysis framework (Sleator and Tarjan 1984), the performance of the online solution obtained under incomplete information is compared with the performance of the offline optimal solution obtained under complete information. The competitive ratio of an online algorithm applied to an online minimization problem is the supremum of the ratio of the cost of the online solution to the cost of the offline optimal solution over all instances of the problem.

Accordingly, a lower bound on the competitive ratio specifies the proximity of the objective function value of an online solution to the optimal objective function value of the offline optimal solution. To derive a lower bound of $LB$ on the competitive ratio of deterministic online algorithms for the $m$-$k$-$CTP,$ we should show that the competitive ratio of any deterministic online algorithm is not less than $LB$ on at least one instance of the $m$-$k$-$CTP.$ We refer the reader to Akbari and Shiri (2022), Akbari, Shiri, and Sibel Salman (2021), Akbari and Shiri (2021), and Shiri and Salman (2019b) for proofs of deriving lower bounds for similar online problems.

3. Findings

Definition 1. For an integer $k,$ a graph is called an adverse graph of order $k$ if it has three connected parts as follows: a left part which is a perfect binary tree (see Appendix A) with $k+1$ levels where the root of the binary tree is the leftmost node, a right part which is a perfect binary tree with $k+1$ levels where the root of the binary tree is the rightmost node, and a bridge part that consists of $2^{k}$ edges such that each one connects a leaf node of the left part to a leaf node of the right part. We call the edges in the bridge part the bridge edges.

Theorem 3.1. No deterministic online algorithm achieves a competitive ratio better than $2\lfloor \frac{k}{\lfloor 2log_2 {L} \rfloor }\rfloor +1$ for the $m$-$k$-$CTP.$

Proof. We assume that the input network $G_{adverse}$ is an adverse graph of order $k$ (Definition 1), where $O$ is the root of the left tree and $D$ is the root of the right tree. We set the traveling time of the bridge edges to 1 and the traveling time of the other edges to 0, i.e., the traveling time of edges on left and right trees are negligible compared to the traveling time of the bridge edges. Figure 1 represents an adverse graph of order 2 with specified values. Note that all the travelers are at $O$ at time 0.

Figure 1.An adverse graph of order 2

Suppose that an arbitrary deterministic online algorithm denoted by $ALG$ ends in time interval $(t^{*},t^{*}+1],$ where $t^{*}$ is a non-negative integer number. Hence, $ALG$ can be represented by set of pairs $\{((i,i+1],L_i)\}$ for $i=0,1,2,...,t^{*},$ where $(i,i+1]$ represents a time interval and $L_i \ (L_i \in \{0,1,2,...,L\})$ denotes the number of travelers which depart from the left tree and enter the right tree by traversing a bridge edge in time interval $(i,i+1].$

Note that level $j \ (j \in \{1,2,...,k+1\})$ consists of $2^{j-1}$ nodes in both the left and right trees. We label the nodes of level $j$ such that $v^{left}_{wj}$ and $v^{right}_{wj}$ represent the $w$th $(w=1,2,...,2^{j-1})$ nodes of the $j$th level on the left and right trees, respectively. For $ALG$ and the node $v^{left}_{wj},$ we let $x^i_{wj}$ denote the number of travelers that depart from the left tree and enter the right tree via $v^{left}_{wj}$ within time interval $(i,i+1]$ for $i = 0,1,2,...,t^{*}.$ For $ALG,$ we assume that the online adversary blocks the edges according to the blocking strategy in Algorithm 1.

We apply the next lemma which is proven in Appendix B to complete the proof.

Lemma 2. The travelers can find at most $\lfloor 2log_2 {L} \rfloor$ blocked edges within time interval $(2i,2i+2]$ for $i = 0,1,2,...,2\lfloor\frac{t^{*}}{2}\rfloor$ in $ALG$ applied to $G_{adverse}$ against the adverse blocking strategy.

It takes at least $\lfloor \frac{k}{\lfloor 2log_2 {L} \rfloor} \rfloor$ time intervals with length 2 from time 0 to find the $k$ blocked edges. It takes one unit of time to arrive at $D$ when all the blocked edges are identified. Thus, no deterministic algorithm terminates earlier than time $2\lfloor \frac{k}{\lfloor 2log_2 {L} \rfloor}\rfloor +1.$ Theorem 3.1 follows since it takes one unit of time from $O$ to $D$ in the offline optimal solution.

It is easy to verify that $L > \lfloor 2log_2 {L} \rfloor$ for integers $L > 4$ and $L = \lfloor 2log_2 {L} \rfloor$ for $L = 2,3,4.$ Hence, $2\lfloor \frac{k}{\lfloor 2log_2 {L} \rfloor }\rfloor +1$ (Theorem 3.1) is a tighter lower bound than $2\lfloor \frac{k}{L }\rfloor +1$ given in the literature. This result implies that the adversarial online blocked edges can have a significant negative effect on network reliability.