Hierarchical Placement and Network Design Problems

Overview

This paper gives the first constant-approximations for a number of layered network design problems. It begins by modeling hierarchical caching, where caches are placed in layers and each layer satisfies a fixed percentage of the demand (bounded miss rates). The paper presents a constant approximation to the minimum total cost of placing the caches and routing demand through the layers. This model is extended to cover more general layered caching scenarios, giving a constant combinatorial approximation to the well studied multi-level facility location problem. This paper considers a facility location variant, the Load Balanced Facility Location problem in which every demand is served by a unique facility and each open facility must serve at least a certain amount of demand.