Abstract
In the fields of communication and transportation, many researchers have been concentrating on location problems. The objective of a location problem is to optimally choose the location of facilities. In network location theory, the shapes of facilities can be points, paths, or trees. A network usually involves two types of parameters: weights of nodes and lengths of edges. Traditionally, the node weights and edge lengths of a network are assumed to be known precisely. However, the weights and lengths of a network may fluctuate or be inaccurate due to poor measurements. Thus, location models involving uncertainty have attracted increasing research efforts in recent years. One of the most important ways for modeling network uncertainty is the minmax regret approach. In this dissertation, we examine the path center, median and centdian problems on the minmax-regret model. Since the three problems on general graphs are NP-hard, we focus on the problems on trees. We present efficient algorithms for the minmax regret path median, path centdian, and path center problems on a tree with uncertain vertex weights. For the minmax regret path median problem, we improve the upper bound from O(n4) to O(n2). For the minmax regret path centdian problem, we show that there is a small bug in the previous solution and show how to rectify the bug; in addition, we further improve the upper bound from O(n5 log n) to O(n4). For the minmax regret path center problem, we improve the previous upper bound from O(n2) to O(n log n).