{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,17]],"date-time":"2025-09-17T16:12:41Z","timestamp":1758125561747},"reference-count":35,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4546,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1994,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The <jats:italic>Geometric Steiner Minimum Tree problem<\/jats:italic> (GSMT) is to connect at minimum cost <jats:italic>n<\/jats:italic> given points (called <jats:italic>terminals<\/jats:italic>) in <jats:italic>d<\/jats:italic>\u2010dimensional Euclidean space. We generalize a GSMT approximation partitioning algorithm by Koml\u00f3s and Shing (KS) and analyze its performance under more relaxed conditions. These generalizations have practical applications for multilayer VLSI routing. Whereas KS assumed <jats:italic>d<\/jats:italic> = 2, our algorithm works for any dimension <jats:italic>d<\/jats:italic> \u2a7e 2. Moreover, whereas their analysis assumed the rectilinear norm and a uniform distribution of input points, our analysis holds for any norm on <jats:italic>R<jats:sup>d<\/jats:sup><\/jats:italic> and whenever the terminals are any independent identically distributed random variables taking on values in any bounded subset of <jats:italic>R<jats:sup>d<\/jats:sup><\/jats:italic>. Both algorithms depend on a parameter <jats:italic>t<\/jats:italic> through which the user can trade off time for solution quality. We evaluate our algorithm in terms of its performance ratio\u2013the 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 <jats:italic>n<\/jats:italic> \u2192 \u221e of the supremum of the performance ratio of our algorithm is 1 + <jats:italic>O<\/jats:italic><jats:italic>t<\/jats:italic><jats:sup>\u22121\/<jats:italic>d<\/jats:italic><\/jats:sup>(<jats:italic>d<\/jats:italic>\u20101), almost surely. This result generalizes the corresponding 1 + <jats:italic>O<\/jats:italic>(<jats:italic>t<\/jats:italic><jats:sup>\u22121\/2<\/jats:sup>) bound proven by KS. Along the way, we prove a useful combinatorial lemma about <jats:italic>d<\/jats:italic>\u2010dimensional rectangle slicings. We prove that the worst\u2010case time and space complexity of our algorithm is \u03b8(<jats:italic>n<\/jats:italic> lg (<jats:italic>n\/t<\/jats:italic>) + <jats:italic>T<\/jats:italic><jats:sub><jats:italic>MST<\/jats:italic><\/jats:sub>(<jats:italic>v, v<\/jats:italic>) + <jats:italic>nT<\/jats:italic><jats:sub><jats:italic>SMT<\/jats:italic><\/jats:sub>(<jats:italic>t<\/jats:italic>)\/<jats:italic>t<\/jats:italic>) and \u03b8(<jats:italic>S<\/jats:italic><jats:sub><jats:italic>MST<\/jats:italic><\/jats:sub>(<jats:italic>v, v<\/jats:italic>) + <jats:italic>S<\/jats:italic><jats:sub><jats:italic>SMT<\/jats:italic><\/jats:sub>(<jats:italic>t<\/jats:italic>)), respectively, where <jats:italic>v<\/jats:italic> \u2a7d <jats:italic>n<\/jats:italic> + 2<jats:sup><jats:italic>d<\/jats:italic>+1<\/jats:sup> (<jats:italic>n\/t<\/jats:italic>) \u03c3(<jats:italic>t<\/jats:italic>) is the number of vertices in the resulting Steiner tree. Here, <jats:italic>T<\/jats:italic><jats:sub><jats:italic>SMT<\/jats:italic><\/jats:sub>(<jats:italic>t<\/jats:italic>) and <jats:italic>S<\/jats:italic><jats:sub><jats:italic>SMT<\/jats:italic><\/jats:sub>(<jats:italic>t<\/jats:italic>) are the time and space required to solve exactly any GSMT problem of size less than <jats:italic>t<\/jats:italic>; <jats:italic>T<\/jats:italic><jats:sub><jats:italic>MST<\/jats:italic><\/jats:sub>(<jats:italic>n, m<\/jats:italic>) and <jats:italic>S<\/jats:italic><jats:sub><jats:italic>MST<\/jats:italic><\/jats:sub>(<jats:italic>n, m<\/jats:italic>) are the time and space required to find a minimum spanning tree of a graph with <jats:italic>n<\/jats:italic> nodes and <jats:italic>m<\/jats:italic> edges; and \u03c3(<jats:italic>t<\/jats:italic>) is the maximum number of Steiner points for any Steiner minimum tree with <jats:italic>t<\/jats:italic> terminals. For example, for <jats:italic>R<\/jats:italic><jats:sup>2<\/jats:sup> and the rectilinear norm, the time is <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic> lg(<jats:italic>n\/t<\/jats:italic>) + <jats:italic>n<\/jats:italic> lg*<jats:italic>n<\/jats:italic> + <jats:italic>nT<\/jats:italic><jats:sub><jats:italic>SMT<\/jats:italic><\/jats:sub>(<jats:italic>t<\/jats:italic>)\/<jats:italic>t<\/jats:italic>) and the space is <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic> lg *n + <jats:italic>S<\/jats:italic><jats:sub><jats:italic>SMT<\/jats:italic><\/jats:sub>(<jats:italic>t<\/jats:italic>)). \u00a9 1994 by John Wiley &amp; Sons, Inc.<\/jats:p>","DOI":"10.1002\/net.3230240303","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T18:18:25Z","timestamp":1178993905000},"page":"147-159","source":"Crossref","is-referenced-by-count":6,"title":["Probabilistic analysis of an enhanced partitioning algorithm for the steiner tree problem in <i>R<sup>d<\/sup><\/i>"],"prefix":"10.1002","volume":"24","author":[{"given":"Konstantinos","family":"Kalpakis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alan T.","family":"Sherman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230070104"},{"key":"e_1_2_1_3_2","volume-title":"Real Analysis and Probability","author":"Ash R. B.","year":"1970"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230170107"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100034095"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1038\/scientificamerican0189-84"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/355759.355764"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758759"},{"key":"e_1_2_1_9_2","unstructured":"E. J.CockayneandD. G.Schiller Computation of Steiner minimal trees.Combinatorics(1972)53\u201371."},{"key":"e_1_2_1_10_2","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"1990"},{"key":"e_1_2_1_11_2","volume-title":"What Is Mathematics?","author":"Courant R.","year":"1941"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758755"},{"key":"e_1_2_1_13_2","volume-title":"Geometric Measure Theory","author":"Federer H.","year":"1969"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300000784"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/0132072"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/0132071"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/0116001"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/0114025"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/0130013"},{"key":"e_1_2_1_21_2","first-page":"553","volume-title":"Probabilistic analysis of an enhanced partitioning algorithm for the Steiner tree problem in Rd. Proceedings of the 13th Annual Allerton Conference on Communication, Control, and Computing","author":"Kalpakis K.","year":"1992"},{"key":"e_1_2_1_22_2","unstructured":"K.KalpakisandA. T.Sherman Probabilistic analysis of an enhanced partitioning algorithm for the Steiner tree problem in Rd. Technical Report CS\u2010TR\u20102936\/UM\u2010IACS\u2010TR\u201092\u201083 University of Maryland College Park (July 1992). Also available in revised form as Technical Report TR CS\u201092\u201010 Computer Science Department University of Maryland Baltimore County."},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2.3.209"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230150403"},{"key":"e_1_2_1_25_2","first-page":"52","volume-title":"Studies in Optimization. Studies in Mathematics, 10","author":"Kuhn H. W.","year":"1974"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1961-016-2"},{"key":"e_1_2_1_27_2","volume-title":"An Introduction to Probability Theory","author":"Moran P. A. P.","year":"1968"},{"key":"e_1_2_1_28_2","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou C. H.","year":"1982"},{"key":"e_1_2_1_29_2","doi-asserted-by":"crossref","unstructured":"J. S.Provan Convexity and the Steiner tree problem.Networks(1988)55\u201372.","DOI":"10.1002\/net.3230180108"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9658-1"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758756"},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176994411"},{"key":"e_1_2_1_33_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.15.4.749"},{"key":"e_1_2_1_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/0150015"},{"key":"e_1_2_1_35_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230150305"},{"key":"e_1_2_1_36_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230170203"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230240303","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230240303","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T19:04:34Z","timestamp":1698174274000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230240303"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,5]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,5]]}},"alternative-id":["10.1002\/net.3230240303"],"URL":"https:\/\/doi.org\/10.1002\/net.3230240303","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,5]]}}}