Approximation algorithms for the multi-level facility location problem

The multi-level generalization of the facility location problem has been conspicuous in its absence from recent results improving the approximation constant for the facility location problem. The facility location problem assigns clients to facilities, paying a service cost for each assignment and a fixed cost for each opened facility. The optimal solution must find a balance between the service costs and the facilities used. The multi-level facility location problem is an important generalization that arises in such contexts as multi-level inventory hierarchies and network design. The optimal solution to this problem seeks a balance between the cost of routing demand via a facility of each level and the cost of installing the facilities used. We will present a number of techniques that make it possible to leverage the recent results for single-level problems to find good solutions for multi-level instances.