Facility Location Optimization Methods Based on Aggregate and Disperse Moves

The hierarchical facility costs are a special case of the setting in which the facility cost is a more complex function of the set of clients assigned to a single facility, and the algorithm for the problem independent of the number of levels in the hierarchy tree, for the case of identical costs on all facilities does not simply depend on their number. We use the aggregate and disperse moves to show that a constant factor approximation algorithm for the facility location problem with hierarchical facility costs, which a locally optimal solution is a 5-approximation for the problem. Using scaling we improve the bound to 4.236, and accepting only sufficiently large improvements, we can turn this into a polynomial time (4.236+epsiv)-approximation algorithm for the hierarchical facility location problem. A more general class of such problems be defined by using a facility cost that is an arbitrary sub-modular function cost(S) of the set of clients S assigned to the facility. Sub-modularity represents a natural economy of scale in handling extra clients at an existing facility.