Report Number: CS-TN-00-93
Institution: Stanford University, Department of Computer Science
Title: Hierarchical Placement and Network Design Problems.
Author: Guha, Sudipto
Author: Meyerson, Adam
Author: Munagala, Kamesh
Date: May 2000
Abstract: In this paper, we give the first constant-approximations for a number of layered network design problems. We begin by modeling hierarchical caching, where caches are placed in layers and each layer satisfies a fixed percentage of the demand (bounded miss rates). We present a constant approximation to the minimum total cost of placing the caches and routing demand through the layers. We extend this model to cover more general layered caching scenarios, giving the first constant approximation to the well studied multi-level facility location problem. We consider 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. By combining Load Balanced Facility Location with our results on hierarchical caching, we give the first constant approximation for the Access Network Design problem.
http://i.stanford.edu/pub/cstr/reports/cs/tn/00/93/CS-TN-00-93.pdf