PROBABILISTIC ANALYSIS OF AN ENHANCED PARTITIONING ALGORITHM FOR THE STEINER TREE PROBLEM IN RD

The Geometric Steiner Minimum Tree problem (GSMT) is to connect at min imum cost n given points (called terminals) in d-dimensional Euclidean space. We generalize a GSMT approximation partitioning algorithm by K omlos and Shing (KS) and analyze its performance under more relaxed co nditions. These generalizations have practical applications for multil ayer VLSI routing. Whereas KS assumed d = 2, our algorithm works for a ny dimension d greater-than-or-equal-to 2. Moreover, whereas their ana lysis assumed the rectilinear norm and a uniform distribution of input points, our analysis holds for any norm on R(d) and whenever the term inals are any independent identically distributed random variables tak ing on values in any bounded subset of R(d). Both algorithms depend on a parameter t through which the user can trade off time for solution quality. We evaluate our algorithm in terms of its performance ratio-t he ratio of the cost of the Steiner tree computed by the algorithm div ided by the cost of a Steiner minimum tree. Applying a probability the orem on subadditive Euclidean functionals by Steele, we prove the foll owing: Under the aforementioned distribution of inputs, the limit as n --> infinity of the supremum of the performance ratio of our algorith m is 1 + O(t-1/d(d-1)), almost surely. This result generalizes the cor responding 1 + O(t-1/2) bound proven by KS. Along the way, we prove a useful combinatorial lemma about d-dimensional rectangle slicings. We prove that the worst-case time and space complexity of our algorithm i s THETA(n lg (n/t) + T(MST)(upsilon, upsilon) + nT(SMT)(t)/t) and THET A(S(MST)(upsilon, upsilon) + S(SMT)(t)), respectively, where upsilon l ess-than-or-equal-to n + 2d+1(n/t)sigma(t) is the number of vertices i n the resulting Steiner tree. Here, T(SMT)(t) and S(SMT)(t) are the ti me and space required to solve exactly any GSMT problem of size less t han t; T(MST)(n, m) and S(MST)(n, m) are the time and space required t o find a minimum spanning tree of a graph with n nodes and m edges; an d sigma(t) is the maximum number of Steiner points for any Steiner min imum tree with t terminals. For example, for R2 and the rectilinear no rm, the time is O(n lg(n/t) + n lgn + nT(SMT)(t)/t) and the space is O(n lgn + S(SMT)(t)). (C) 1994 John Wiley & Sons, Inc.