Closing the Gap: Near-Optimal Steiner Trees in Polynomial Time

Report
Authors:Barrera, Tim, Department of Computer ScienceUniversity of Virginia Griffith, Jeff, Department of Computer ScienceUniversity of Virginia Robins, Gabriel, Department of Computer ScienceUniversity of Virginia Zhang, Tongtong, Department of Computer ScienceUniversity of Virginia
Abstract:

We propose several efficient enhancements to the Iterated 1-Steiner (I1S) heuristic of Kahng and Robins [17] for the minimum rectilinear Steiner tree problem. For typical nets, our methods obtain average performance of less than 0.25% from optimal, and produce optimal solutions up to 90% of the time. We generalize IIS and its variants to three dimensions, as well as to the case where all the pins lie on is parallel planes, which arises in, e.g., multi-layer routing. Our algorithms are highly parallelizable, and extend to arbitrary weighted graphs, and thus, our methods are applicable in practical routing regimes. We prove that given a pointset in the Manhattan plane, the minimum spanning tree (MST) degree of any specific point can be made to be 4 or less; similarly, we show that in three dimensions, the MST degree of any specific point can be made 14 or less. Using a perturbative argument, these results have been recently extended to show that for every pointset in the Manhattan plane there exists an MST with maximum degree 4, and for three-dimensional Manhattan space the maximum MST degree is 14 [28]. Aside from having independent theoretical interest, these results help reduce the running times of our algorithms.
Note: Abstract extracted from PDF file via OCR

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Barrera, Tim, Jeff Griffith, Gabriel Robins, and Tongtong Zhang. "Closing the Gap: Near-Optimal Steiner Trees in Polynomial Time." University of Virginia Dept. of Computer Science Tech Report (1993).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
1993