PRACTICAL APPROXIMATION ALGORITHMS FOR ZERO-AND BOUNDED-SKEW TREES.

The skew of an edge-weighted rooted tree is the maximum difference between any two root-to-leaf path weights. Zero- or bounded-skew trees are needed for achieving synchronization in many applications, including network multicasting [G. N. Rouskas and I. Baldine, IEEE 1. on Selected Areas in Communication, 15 (1997), pp. 346-3561 and VLSI clock routing [H. Bakoglu, Circuits, Interconnections, and Packaging for VSLI, Addison-Wesley, Reading, MA, 1990, A. B. Kahng and G. Robins, On Optimal Interconnections for VSLI, Kluwer Academic Publishers, Norwell, MA, 1995]. In these applications edge weights represent propagation delays, and a signal generated at the root should be received by multiple recipients located at the leaves (almost) simultaneously. The objective is to find zero- or bounded-skew trees of minimum total weight, since the weight of the tree is directly proportional to the amount of resources (bandwidth and buffers for network multicasting, power and chip area for clock routing in VLSI) that must be allocated to the tree. Charikar et al. in [Proceedings of the Tenth ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, 1999, ACM, New York, 1999, pp. 177-1841 have recently proposed the first strongly polynomial algorithms with proven constant approximation factors, 2e≈ 5.44 and 16.86, for finding minimum weight zero- and bounded-skew trees, respectively. In this paper we introduce a new approach to these problems, based on zero-skew "stretching" of spanning trees, and obtain algorithms with improved approximation factors of 4 and 14. For the case when tree nodes are points in the plane and edge weights are given by the rectilinear metric our algorithms find zero- and bounded-skew trees of length at most 3 and 9 times the optimum. This case is of special interest in VLSI clock routing. An important feature of our algorithms is their practical running time, which is asymptotically the same as the time needed for computing the minimum spanning tree. [ABSTRACT FROM AUTHOR]