Single facility collection depots location problem in the plane

In this paper we consider an extension of the classical facility location problem where besides n weighted customers, a set of p collection depots are also given. In this setting the service of a customer consists of the travel of a server to the customer and return back to the center via a collection depot. We have analyzed the problem and showed that the collection depots problem using the Euclidean metric can be transformed to O(p2n2) number of different classical facility location problems and this bound is tight. We then show the existence of small coresets for these problems. These coresets are then used to provide (1+ϵ)-factor approximation algorithms which have linear running times for fixed customer weights and ϵ.