The Obnoxious, Semi-obnoxious And Backup P-median Problems

The facility location is one of major research context in Operations Research Theory, in which mathematical science has attracted much attention in discrete and continuous optimization over nearly last four decades. It has a wide range of important applications, such as communication networks, complex networks, transportation and management science. Facility location problems locate a set of facilities (resources) to minimize the cost of satisfying some set of demands (of the customers) with respect to some set of constraints.Investigators have focused on facility location problems for services (e.g., hos-pitals, post stations, etc.). Recently, the models of obnoxious (e.g., garbage dump sites, chemical plants, etc.), semi-obnoxious (e.g., airport, etc.) and backup p-median problems were proposed. In this thesis, we investigate several types of discrete lo-cation models. By applying graphic and combinatorial optimization algorithms, we mainly study these problems on some special graphs. By analyzing the topol-ogy structures of these special graphs, the polynomial time algorithms for these problems are designed.In Chapter 1, we briefly introduce the practical significance and the research review of the obnoxious, semi-obnoxious and backup p-median problems, define the terminology involved in this thesis and propose the definition of these special graphsIn Chapter 2. we consider the p-maxian problem on a block graph and an interval graph respectively where each edge length on both graphs is unit. On a block graph, we prove that if one point set X contains two points with maximun distance and |X|=p, then X is an optimal solution of the p-maxian problem. And we design a linear time algorithm for this problem (J. Comb. Optim. (2008) DOI 10.1007/s10878-008-9198-1). On an interval graph, we prove that if one interval set X contains two intervals with the minimum right endpoint and the maximum left endpoint respectively and |X|=p, then X is an optimal solution of the p-maxian problem. Then we can solve this problem in linear time.The semi-obnoxious p-median problem is also called the pos/neg-weighted p-median problem. In Chapter 3, we consider the pos/neg-weighted 2-median problem on an interval graph and the pos/neg-weighted 1-median problem on a tree with subtree-shaped customers. For the first problem, we propose two O(n2) time algorithms for the MWD and WMD model respectively (accepted by OR Transactions). For the second problem, the customers are modeled as continua subtrees. We devise a polynomial time algorithm to solve this problem (Theor. Comput. Sci.411 (2010),1038-1044).In Chapter 4, we consider the backup 2-median problem on a cycle and a block graph respectively. First, we prove that the vertex optimality property holds for the backup p-median problem. Based on this property, we devise an O(n2) time algorithm for backup 2-median problem on a cycle. For the backup 2-median problem on a block graph with unit edge lengths, we try to find the relationship of the optimal solutions on a block graph and on its weighted skeleton and propose an O(nlogn+m) time algorithm by using the algorithm for this problem on a tree.