# 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