COST-DISTANCE: Two metric network design

Conference Paper

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 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, constructing single source multicast trees with good cost and delay properties, and multi-level facility location. Our algorithm is also easier to implement and significantly faster than previously known algorithms for buy-at-bulk design problems.

Duke Authors

Cited Authors

  • Meyerson, A; Munagala, K; Plotkin, S

Published Date

  • December 1, 2000

Published In

Start / End Page

  • 624 - 630

International Standard Serial Number (ISSN)

  • 0272-5428

Citation Source

  • Scopus