Design And Analysis Of Algorithm For The K-Product Uncapacitated Facility Problem

Location Problem is a kind of important combinatorial optimization problem and have extensive applications within production management, network communication and computer theory.It can make decision about the location of the network server,nuclear power plant and logistics center.We study k-production uncapacitated facility location problem (k-PUFLP)which was firstly proposed by Huang and Li(2007)based on metric space in this paper.Huang and Li also show a 2k-1 heuristic algorithm.In Section one,this paper briefly introduces some definitions, notations and related information about facility location and describes several characteristics of k-PUFLPN.Section two mainly studies the Integer model and Linear model of k-product uncapacitated location problem.A(3/2)k-1 improved algorithm for solving the k-PUFLPN(k≥2)has been proposed by us.We also discuss the integrality gap of the 2-PUFLPN's linear programming.In the end,we summary and prospect the facility location problem.