Report Number: CS-TN-00-96
Institution: Stanford University, Department of Computer Science
Title: Improved Combinatorial Algorithms for Single Sink Edge Installation Problems.
Author: Guha, Sudipto
Author: Meyerson, Adam
Author: Munagala, Kamesh
Date: June 2000
Abstract: We present the first constant approximation to the single sink buy-at-bulk network design problem, where we have to design a network by buying pipes of different costs and capacities per unit length to route demands at a set of sources to a single sink. The distances in the underlying network form a metric. This result improves the previous bound of log |S|, where S is the set of sources. We also present an improved constant approximation to the related Access Network Design problem. Our algorithms are randomized and fully combinatorial. They can be derandomized easily at the cost of a constant factor loss in the approximation ratio.
http://i.stanford.edu/pub/cstr/reports/cs/tn/00/96/CS-TN-00-96.pdf