| In this thesis we examine a number of facility location problems. The goal of a facility location problem is to find the best possible sites for facilities servicing a client network. The number of available facilities, the type of network and the measure of quality of a solution are all specific to the problem at hand. In our work, all underlying client networks will be trees.; The first set of problems we look at is related to the so-called p-median problem in which each client is assigned a positive weight and p facilities must be placed in order to minimize the sum of the weighted distance from clients to their nearest facility. When p = 1 a very simple algorithm is presented to update the optimal solution each time a modification is made to the network. This simple algorithm is used to find an elegant algorithm for p = 2. Further modifications are made to the algorithm so that its running time matches the lower bound for special types of tree networks.; The positive-negative p-median is a related problem in which the clients are not restricted to positive weights. We present the first sub-quadratic algorithm for the case of p = 2.; The last problem we examined is related to the p-cover problem in which each client, in addition to a weight, is assigned a spanning distance. Clients can only reach facilities located within their spanning distance. The problem is to place the p facilities to maximize the sum of the weights of reachable clients. We present an improved algorithm for the 1-cover problem and show how to apply it to solve the k nearest neighbour problem on trees. |
