Abstract
Network location theory was traditionally concerned under the assumption that the vertex weights and edge lengths in the network are known precisely. However, in reality, these values usually involve uncertainty and cannot be estimated accurately. Recently, increasing research efforts have been devoted to minmax-regret location problems, in which uncertainty of network parameters are characterized by intervals and the goal is to minimize the worst case loss in the objective function. The well-known p-median problem is NP-hard on general networks, but admits an efficient O(pn^2)-time algorithm on trees. So far, even on trees, there is no polynomial-time algorithm for the p-median problem on the minmax-regret model with p >= 2. In this thesis, we study the minmax-regret 2-median problem on a tree, in which each edge is associated with a non-negative length and the weight of each vertex is uncertain. A naïve approach to this problem requires O(n^5) time. In this thesis, a more efficient algorithm is presented, which requires O(n^4) time. The main idea of our O(n^4)-time algorithm is to utilize bisectors between vertices, where a bisector is an edge containing the middle point of the path between two vertices.