Network Design White Papers
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.
| Publisher | Stanford University | File Format | |
|---|---|---|---|
| Date Published | January 2007 | ||
| Format | White Papers | ||
| Topics | |||
-
Did you find this white paper useful? 4 out of 5 users found this white paper useful
White Paper RSS
Download
Register
