Report Number: CS-TN-00-92
Institution: Stanford University, Department of Computer Science
Title: Cost-Distance: Two Metric Network Design
Author: Meyerson, Adam
Author: Munagala, Kamesh
Author: Plotkin, Serge
Date: February 2000
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.
http://i.stanford.edu/pub/cstr/reports/cs/tn/00/92/CS-TN-00-92.pdf