关键词: 近似算法, 计算复杂性, 工厂选址

Abstract: A k-product facility location problem can be described as follows.There is a set of clients and a set of sites where facilities can be set up.Now each client needs to be supplied with k kinds of products and a facility can be set up to supply only one product.Suppose that these facilities considered are relatively centralized，i.e.，the distance between any two facilities is not more than the distance between any facility and client.Assuming that the fixed setup costs are zero，this paper shows that the problem is NP-complete when k=2 and proposes a 2-1/k approximation algorithm for any integer k.In addition an approximation algorithm with worst case ratio not more than 2 is given for the case that the fixed setup costs are not zero.

Key words: approximation algorithm, computational complexity, facility location