Incremental Facility Location Problem and Its Competitive Algorithms

We consider the incremental version of the k-Facility Location Problem, which is a common generalization of the facility location and the k-median problems. The objective is to produce an incremental sequence of facility sets F-1 subset of F-2 subset of...subset of F-n, where each F-k contains at most k facilities. An incremental facility sequence or an algorithm producing such a sequence is called c-competitive if the cost of each F-k is at most c times the optimum cost of corresponding k-facility location problem, where c is called competitive ratio. In this paper we present two competitive algorithms for this problem. The first algorithm produces competitive ratio 8 alpha, where alpha is the approximation ratio of k-facility location problem. By recently result (Zhang, Theor. Comput. Sci. 384: 126-135, 2007), we obtain the competitive ratio 16 + 8 root 3 + epsilon. The second algorithm has the competitive ratio Delta + 1, where Delta is the ratio between the maximum and minimum nonzero interpoint distances. The latter result has its self interest, specially for the small metric space with Delta <= 8 alpha - 1.