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

摘要： k-种产品工厂选址问题是：给定一个客户集合和一个可以建立工厂的地址集合，每个客户需要k-种产品，一个工厂只能为客户提供一种产品。考虑的工厂假设相对集中，即假设任何工厂之间的距离都不大于工厂与客户之间的距离。对于没有建厂费用的问题，当k=2时证明了它是一个NP完全问题，对任意的k给出了一个最坏性能比不大于2-1/k的近似算法。对于有建厂费用的问题，给出了一个最坏性能比不大于2的近似算法。

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