Premium
Probabilistic analysis of an enhanced partitioning algorithm for the steiner tree problem in R d
Author(s) -
Kalpakis Konstantinos,
Sherman Alan T.
Publication year - 1994
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230240303
Subject(s) - steiner tree problem , mathematics , combinatorics , subadditivity , minimum spanning tree , discrete mathematics , approximation algorithm , bounded function , norm (philosophy) , upper and lower bounds , dimension (graph theory) , mathematical analysis , political science , law
The Geometric Steiner Minimum Tree problem (GSMT) is to connect at minimum cost n given points (called terminals ) in d ‐dimensional Euclidean space. We generalize a GSMT approximation partitioning algorithm by Komlós and Shing (KS) and analyze its performance under more relaxed conditions. These generalizations have practical applications for multilayer VLSI routing. Whereas KS assumed d = 2, our algorithm works for any dimension d ⩾ 2. Moreover, whereas their analysis assumed the rectilinear norm and a uniform distribution of input points, our analysis holds for any norm on R d and whenever the terminals are any independent identically distributed random variables taking 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–the ratio of the cost of the Steiner tree computed by the algorithm divided by the cost of a Steiner minimum tree. Applying a probability theorem on subadditive Euclidean functionals by Steele, we prove the following: Under the aforementioned distribution of inputs, the limit as n → ∞ of the supremum of the performance ratio of our algorithm is 1 + O t −1/ d ( d ‐1), almost surely. This result generalizes the corresponding 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 is θ( n lg ( n/t ) + T MST ( v, v ) + nT SMT ( t )/ t ) and θ( S MST ( v, v ) + S SMT ( t )), respectively, where v ⩽ n + 2 d +1 ( n/t ) σ( t ) is the number of vertices in the resulting Steiner tree. Here, T SMT ( t ) and S SMT ( t ) are the time and space required to solve exactly any GSMT problem of size less than t ; T MST ( n, m ) and S MST ( n, m ) are the time and space required to find a minimum spanning tree of a graph with n nodes and m edges; and σ( t ) is the maximum number of Steiner points for any Steiner minimum tree with t terminals. For example, for R 2 and the rectilinear norm, the time is O ( n lg( n/t ) + n lg* n + nT SMT ( t )/ t ) and the space is O ( n lg *n + S SMT ( t )). © 1994 by John Wiley & Sons, Inc.