Research on Computational Complexity and Approximation Algorithm for General Facility Location Problem

Facility location problem, i.e. UFL problem, is an NP-hard combinatorial optimization problem, and one of the hot topics in clustering problem. It has important application in data mining and classification and ranking. Research on approximation algorithms for the problem has been a focus of computer scientists for many years. However, most of the existing results are based on the metric space. The results for the problem in general distance space have not been found all the time. For the facility location problem in general distance space where the maximum connection cost is at most ω>1 times the minimum connection cost, by making use of set cover problem and the method of problem reduction, it is first proved that there are no polynomial time approximation algorithms with approximation ratios smaller than 1.243+0.316ln(ω-1), unless NPDTIME(n\+O(log log n)), and then a (1+ω)/α local search approximation algorithm for the general facility location problem is proposed, where ω>1, 1≤α≤2. Finally, experimental results show that the quality of solutions obtained by the local search algorithm is remarkable. Through elaborate experiment, the local search algorithm is explored further and the improved method for it is proposed.