Algorithm Design And Analysis For Some K-product Uncapacitated Facility Location Problems

k-product uncapacitated facility location problem(k-PUFLP)can be described as follows.There is a set of customers and a set of potential sites where facility can be set up.There are k different products.Each customer needs to be served with all of the k different products and each facility can be set up to provide exact one product with a non-negative fixed cost determined by the product it is designated.The problem is to select a set of facility to be set up and determine an assignment for each customer to a set of k facilities to provide it with k distinct products.It is assumed that the capacity of any facility is unlimited and there is a non-negative cost for shipping products between each pair of locations.The aim is to minimize the sum of the setup costs and the shipping costs from facilities to customers.For k-PUFLP,when the cost of setting up any facility is zero,we denote by k-PUFLPN.When k?3,the approximation ratio of an existing algorithm is improved to 3k/2-3/2.For the robust k-product uncapacitated facility location problem(Robust k-PUFLP),a constant q is given as the upper bound of the number of outliers,and a maximum of q customers are allowed to be unserved.For this problem,when k? 3 and the cost of setting up any facility is zero,we addressed an approximation algorithm with an approximate ratio of 3k/2-3/2.For the robust k-product uncapacitated facility location problem with linear penalties(Robust k-PUFLPLP),both outliers and penalties should be taken into consideration.A detailed description of this problem is that,on the basis of k-product uncapacitated facility location problem,a constant q is given as the upper bound of the number of outliers,and each customer has a linear penalty cost.Robust k-PUFLPLP is similar to Robust k-PUFLP in that,each facility can be set up to provide exact one product,and a maximum of q customers are allowed to be unserved.The difference between them lies in that,in Robust kPUFLPLP,non-outliers are also allowed to be unserved,but the corresponding penalty cost should be paid.The objective is to determine an opening facility set,specify the products produced by each opening facility,connect some of the customers to opening facilities to meet these customers' needs of the k products,ignore the outlier customers,and penalize the remaining customers,such that the sum of the facility opening cost,the connection cost and the penalty cost is minimized.In this thesis,we established a model for the robust k-product uncapacitated facility location problem with linear penalties and no fixed costs.When k? 3,by exploiting the special structure of the problem,we design a 3/2k-3/2 approximation algorithm based on the linear rounding technique.