BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TN-00-93
       ENTRY:: May 15, 2000
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Hierarchical Placement and Network Design Problems.
        TYPE:: Technical Note
      AUTHOR:: Guha, Sudipto
      AUTHOR:: Meyerson, Adam
      AUTHOR:: Munagala, Kamesh
        DATE:: May 2000
       PAGES:: 19
    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.
       NOTES:: [Adminitrivia V1/Prg/20000515]
         END:: STAN//CS-TN-00-93