| On Approximation of the Power-p and Bottleneck Steiner Trees Piotr (2007) | |||||||||||||||
Abstract | |||||||||||||||
| Many VLSI routing applications, as well as the facility location problem involve computation of Steiner trees with non-linear cost measures. We consider two most frequent versions of this problem. In the power-p Steiner problem the the cost is defined as the sum of the edge length raised to power p, while in the bottleneck Steiner problem the cost is the maximum of the edge lengths. In contrast to the classical Steiner problem, the objective of the power-p and bottleneck Steiner tree problems is to minimize the sum of the edge lengths raised to the p power or the maximum edge length, respectively. We show that the both problems are NP-hard and, moreover, the bottleneck Steiner trees cannot be approximated with the factor less than 2, unless P = NP. We prove that the minimum spanning tree only constant times worse than the power-p Steiner tree in any metric space. In particular, for p = 2, we show that the minimum spanning tree is at most 23.3 times worse than the optimum and construct an instance when it is 17.2 times worse. We also present a better approximation algorithm for the bottleneck Steiner problem with performance guarantee log 2 n, where n is the number of terminals (the minimum spanning tree can be 2 log 2 n times worse than the optimum). 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||