BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TN-00-92
       ENTRY:: February 28, 2000
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Cost-Distance: Two Metric Network Design
        TYPE:: Technical Note
      AUTHOR:: Meyerson, Adam
      AUTHOR:: Munagala, Kamesh
      AUTHOR:: Plotkin, Serge
        DATE:: February 2000
       PAGES:: 10
    ABSTRACT:: We present the Cost-Distance problem: finding a Steiner tree
               which optimizes the sum of edge costs along one metric and
               the sum of source-sink distances along an unrelated second
               metric. We give the first known O(log k) randomized
               approximation scheme for Cost-Distance, where k is the number
               of sources. We reduce many common network design problems to
               Cost-Distance, obtaining (in some cases) the first known
               logarithmic approximation for them. These problems include
               single-sink buy-at-bulk with variable pipe types between
               different sets of nodes, and facility location with
               buy-at-bulk type costs on edges. Our algorithm is also the
               algorithm of choice for several previous network design
               problems, due to its ease of implementation and fast running
               time.
       NOTES:: [Adminitrivia V1/Prg/20000228]
         END:: STAN//CS-TN-00-92