In the online multi-agent-Canadian Traveler Problem - - an undirected connected network with a given source node and a destination node together with non-negative edge costs are given. There are travelers in the network who are initially located at and can communicate with each other in real time. There are 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 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 to with minimum total cost of the edges travelled. From a network resilience perspective, the - - 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 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 - - by means of competitive ratio described in section 2. A lower bound of 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 - - which is tighter than the lower bound of given in the literature.
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 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.on the competitive ratio of deterministic online algorithms for the - - we should show that the competitive ratio of any deterministic online algorithm is not less than on at least one instance of the - - We refer the reader to
Definition 1. For an integera graph is called an adverse graph of order if it has three connected parts as follows: a left part which is a perfect binary tree (see Appendix A) with levels where the root of the binary tree is the leftmost node, a right part which is a perfect binary tree with levels where the root of the binary tree is the rightmost node, and a bridge part that consists of 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 thanfor the - -
Proof. We assume that the input network Figure 1 represents an adverse graph of order 2 with specified values. Note that all the travelers are at at time 0.is an adverse graph of order (Definition 1), where is the root of the left tree and 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.
Suppose that an arbitrary deterministic online algorithm denoted byends in time interval where is a non-negative integer number. Hence, can be represented by set of pairs for where represents a time interval and denotes the number of travelers which depart from the left tree and enter the right tree by traversing a bridge edge in time interval
Note that level Algorithm 1.consists of nodes in both the left and right trees. We label the nodes of level such that and represent the th nodes of the th level on the left and right trees, respectively. For and the node we let denote the number of travelers that depart from the left tree and enter the right tree via within time interval for For we assume that the online adversary blocks the edges according to the blocking strategy in
We apply the next lemma which is proven in Appendix B to complete the proof.
Lemma 2. The travelers can find at mostblocked edges within time interval for in applied to against the adverse blocking strategy.
It takes at leasttime intervals with length 2 from time 0 to find the blocked edges. It takes one unit of time to arrive at when all the blocked edges are identified. Thus, no deterministic algorithm terminates earlier than time Theorem 3.1 follows since it takes one unit of time from to in the offline optimal solution.
It is easy to verify thatfor integers and for Hence, (Theorem 3.1) is a tighter lower bound than given in the literature. This result implies that the adversarial online blocked edges can have a significant negative effect on network reliability.