Research On Facility Location Problems And Their Applications

Facility location problems are a collection of optimization problems and they are widely studied and applied in variable areas such as networks, distributed computation, operation research and data mining. It is of great practical significance to study kinds of facility location problems. The common form of facility location problems is to select a subset of objects from a given set to serve all other objects. The goal of optimization is to minimize the service cost. For example, some proxies are selected from a LAN to minimize the delay time inccured by other network hosts when accessing the external network. The following research work on some form of facility location problems is presented.The complete coverage problem in undirected trees and its application was studied, which is a restricted form of the 1-coverage problem in undirected trees and also a generalized form of the 1-median problem in undirected trees. An elegant O ( n log n ) time algorithm was proposed to solve this problem. The algorithm can be applied to select the best proxy or web cache server in a tree based network.An improved algorithm for p-coverage problem on a line was proposed, which was based on the existing dynamic programming algorithm and make use of efficient data structure and query optimization techniques. The improved time complexity and space complexity are O ( np log n ) and O ( n log n ), respectively, while the time complexity and space complexity of original algorithm are both O ( n 2).The k-nodes core of an undirected tree and its applications were proposed and studied. This problem is a restricted form of the k-tree core of an undirected tree and is motivated from the application in the design of distributed data base in tree based network. Two dynamic programming algorithms were proposed to solve this problem, one of which was easy to implement and the other was of great time efficiency but more complex. Two algorithms can be applied under different circumstances.The dynamic form of the 1-median problem in an undirected tree was studied. This dynamic form requires that the 1-median of an undirected tree be maintained subject to changing the weights of the tree nodes. A simple algorithm making use of dynamic tree data structures and maintaining 1-median of an undirected tree subject to changes of node weights in logarithmic time was proposed, and solve the problem that the existing algorithm can't handle the case where a node weight increases. The p-median of an undirected tree problem was studied. An algorithm of much lower time complexity than the existing algorithms was proposed. Although the proposed algorithm was unable to solve all input instances and some special input instances make it fail, experiments show that it was able to solve most of input instances.