A POLYNOMIAL-TIME DUAL ALGORITHM FOR THE EUCLIDEAN MULTIFACILITY LOCATION PROBLEM

The Euclidean multi-facility location (EMFL) problem is one of locatin g new facilities in the Euclidean space with respect to existing facil ities. The problem consists of finding locations of new facilities whi ch will minimize a total cost function which consists of a sum of cost s directly proportional to the Euclidean distances between the new fac ilities, and costs directly proportional to the Euclidean distances be tween new and existing facilities. In this paper, it is shown that the dual of EMFL proposed by Francis and Cabot is equivalent to the maxim ization of a linear function subject to convex quadratic inequality co nstraints and therefore can be solved in polynomial time by interior p oint methods. We also establish a theorem on the duality gap and prese nt a procedure for recovering the primal solution from an interior dua l feasible solution.