关键词: 近似算法, 工厂选址, k-种产品

Abstract: A k-product uncapacitated facility location problem can be described as follows.There is a set of clients and a set of potential sites where facilities can be set up.There are k different kinds of products.Each client needs to be supplied with k kinds of products by a set of k different facilities and each facility can be set up to supply only a distinct product with a non-negative fixed cost.There is a nonnegative cost of shipping goods between each pair of locations.These costs are assumed to be symmetric and satisfy the triangle inequality within the problem.The problem is to select a set of facilities to be set up and their designated products and to find an assignment for each client to a set of k facilities.The optimal goal of this problem is to minimize the sum of the setup costs and the shipping costs.Assuming that fixed setup cost are zero，we have gived a 3k/2-1 approximation algorithm for the problem.

Key words: approximation algorithms, facility location, k-product