Cost-Distance: Two Metric Network Design

Download Now Free registration required

Executive Summary

This paper 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. Authors give the first known 0(log k) randomized approximation scheme for Cost-Distance, where k is the number of sources. Authors reduce several 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, facility location with buy-at-bulk type costs on edges (integrated logistics), constructing single source multicast trees with good cost and delay properties, priority Steiner trees, and multilevel facility location.

  • Format: PDF
  • Size: 186.5 KB