Lena Leiß

• Facility location planning problems are a well-studied topic in optimization - and for good reason. Their applications appear in lots of different areas of real life. In this thesis, we study location problems in the context of parametric networks, where the parameter is introduced on the weights of the edges. Furthermore, interdiction location problems are analyzed, that include an opposing force - the interdictor - with the goal to destroy the existing network by removing edges of the network to make the situation as unfavorable as possible for the locator. In the first part of the work, we investigate location problems in the context of parametric optimization. Here, we assume that the edge weights in the considered networks are linearly dependent on a parameter lambda. Parametric optimization has been studied in relation to many other classical optimization problems; however, so far, there have been no results on location problems in networks with parametric edge weights. For this purpose, we analyze the classical 1-median and 1-center problems on general graphs and also on trees. In doing so, we examine the complexity of both the solution itself and the objective function value as a function of the parameter. We emphasize that the complexity of the optimal value function can be super-polynomial on directed general graphs for both median and center problems, which motivates the development of approximation schemes for these cases. In fact, approximation methods that rely on an existing approximation scheme are introduced for both location problems on directed and undirected general graphs. The developed method is based on the fact that both median and center problems can be divided into subproblems, that get approximated individually before combining the gained information into an overall approximate solution without losing the initial approximation guarantee. Furthermore, exact algorithms are given for the two considered parametric location problems on both directed and undirected trees. These algorithms exploit the properties of trees - precisely the uniqueness of the shortest paths in said structures. In the second part of the thesis, we introduce the p-median interdiction problem on trees. The goal of the interdictor is to remove edges of the underlying network to deteriorate the initial situation of the locator in order to worsen their objective function value. In this part, we first show that the p-median interdiction problem on trees is NP-complete by a reduction from the knapsack problem with bounded profit ratio of 2. Furthermore, we present algorithms for solving the problem on paths with unit and arbitrary lengths. Finally, an exact algorithm is presented for trees with unit edge weights and a single interdiction. Let e be the edge that is incident to the leaf that is nearest to the median location of the initial tree. We prove that removing this edge is the optimal interdiction strategy.