Analysis of online optimization problems in navigation and search on networks

In this thesis, we study online optimization problems that are related to navigation and search on networks. In online problems information is revealed incrementally, and decisions must be made before all information is available. We design and analyze strategies for several online problems with applications in disaster response, search-and-rescue, security, and defense. We prove worst-case competitive ratios to analyze the performance of the proposed strategies. We first study the online k-Canadian Traveler Problem (k-CTP) on O-D edge-disjoint graphs. An optimal randomized strategy was given in the literature. We prove that the given strategy cannot be implemented in some cases and modify it such that it is optimal and can be implemented in all cases. We consider the online multi-agent k-CTP. We derive improved lower bounds on the competitive ratio of deterministic strategies for the cases with limited and complete communication. We introduce two deterministic strategies and show that one of them is optimal in both cases with complete and limited communication on O-D edge-disjoint graphs. We provide lower bounds on the competitive ratio of randomized strategies for the cases without communication, with limited communication and with complete communication. We introduce a randomized online strategy which is optimal for both cases with limited and complete communication on O-D edge-disjoint graphs. We also consider the online Minimum Latency Problem with edge uncertainty. We present an optimal deterministic strategy. Moreover, we present a lower bound on the expected competitive ratio of randomized strategies. Finally, we investigate the online Discrete Search Problem with traveling and search costs on undirected graphs. We propose tight competitiveness lower bounds together with optimal deterministic and randomized strategies.