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⊆F
2⊆…⊆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α, where α 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√3+ϵ. The second algorithm has the competitive ratio Δ+1, where Δ 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 Δ≤8α-1.
