Continuous Facility Location with Backbone Network Costs

We consider a continuous facility location problem in which our objective is to minimize the weighted sum of three costs: (1) fixed costs from installing the facilities, (2) backbone network costs incurred from connecting the facilities to each other, and (3) transportation costs incurred from providing services from the facilities to the service region. We first analyze the limiting behavior of this model and derive the two asymptotically optimal configurations of facilities: one of these configurations is the well studied honeycomb heuristic, and the other is an Archimedean spiral. We then give a fast constant-factor approximation algorithm for finding the placement of a set of facilities in any convex polygon that minimizes the sum of the three aforementioned costs.