The Semi-Obnoxious And Obnoxious P-median And The General Location Problem With Connectivity

The facility location problem is an important branch of research fields within Operations Research Theory and has an important and wide applications in the ranges of communication, logistics and military, such as plants, warehouses, emer-gency centers, firehouses, waste disposal centers, logistics centers and missile warehouses, etc. A suitable location for service facilities could improve the ef-ficiency of enter-prises, the quality of governments and the safety of militaries, and thus enhance the profit and competitiveness, credibility and combat capa-bility, respectively. Therefore, the theory of facility location has a considerable significance in economy, society and military.Researchers have focused on facility location problems for public service fa-cilities (e.g., hospitals, banks and post offices, etc.). Recently, the models for semi-obnoxious (e.g., airports, etc.), obnoxious (e.g., chemical plants, etc.) and connected facilities (server, etc.) were proposed, which are of more practical ap-plication than classical ones. In this thesis, we investigate several types of discrete location models, i.e., the semi-obnoxious, obnoxious p-median problems, and the general location problem with connectivity on some special graphs, as well as the least central subtrees of a tree. By analyzing the topological structures of these graphs, and applying combinatorial optimization methods, the polynomial time algorithms for these problems are designed, and the properties of the tree are characterized for the least central subtrees.In Chapter1, we briefly introduce practical backgrounds and research pro-gresses of the semi-obnoxious, obnoxious p-median problems and the general loca-tion problems with connectivity, and then propose the definitions of some special graphs and the terminologies, notations which will be used in this thesis.The semi-obnoxious p-median problem is also called the pos/neg-weighted p-median problem. In Chapter2, we consider the pos/neg-weighted2-median problems on trees and balanced trees respectively, where each customer is subtree- shaped. For the problem on a tree, we deal with the MWD and WMD models, and propose O(max{mn, n2}) and O(mn2) time algorithms, respectively. For the problem on a balanced tree, all customers are restricted to be disjoint. We devise a polynomial time algorithm of complexity O(n log n).The obnoxious p-median location problem is also called the p-maxian prob-lem. In Chapter3, we consider the p-maxian problem on cactus graphs with arbitrary vertex weights. We first construct a modified graph for the cactus graph, and then show that the p-maxian problem on the modified graph fulfills the "vertex optimality property". For the2-maxian problem on the modified graph, we prove that in the worst case, the midpoint of any path connecting mi and m2, where{m1, m2} is the2-maxian of the cactus, lies on a specified cycle. Based on this property, we develop a dynamic programming algorithm with time complexity of O(n2) for the problem.In Chapter4, we study the general location problem with connectivity, i.e., the induced graph by any solution vertices is connected. We show that the general location problem on chordal bipartite graphs is NP-hard. For the problem on a tree, we first analysis the structures of vertex levels and edge sequence of the tree, and then present a dynamic programming algorithm with time complexity of O(np2). Furthermore, we improve the time complexity to O(np) in the case where the underlying graph is an equivalent binary tree.In Chapter5, we investigate the least central subtree of a tree. We char-acterize the trees having two adjacent vertices as a unique least central subtree. Furthermore, we generalize the least central subtree of a tree to a weighted tree. We show that each least central subtree of a weighted tree either contains a vertex of the ω-centroid or is adjacent to the ω-centroid. Also, we show that any two least central subtrees of a weighted tree either have a nonempty intersection or are adjacent.