On the performance bounds for a class of rectilinear Steiner tree heuristics in arbitrary dimension
- 1 January 1992
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 11 (11) , 1462-1465
- https://doi.org/10.1109/43.177409
Abstract
A family of examples on which a large class C of minimum spanning tree-based rectilinear Steiner tree heuristics has a performance ratio arbitrarily close to 3/2 times optimal is given. The class C contains many published heuristics whose worst-case performance ratios were previously unknown. Of particular interest is that C contains two heuristics whose worst-case ratios had been conjectured to be bounded away from 3/2, and the construction also points out an incorrect claim of optimality for one of these heuristics. The examples also force the worst possible behavior in a number of heuristics outside C. The construction generalizes to d dimensions, where the heuristics will have performance ratios of at least 2d - 1/d; this improves the previous lower bound on performance ratio in arbitrary dimensionKeywords
This publication has 18 references indexed in Scilit:
- A new global router for row-based layoutPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A tight worst case bound for the performance ratio of heuristics for the minimum rectilinear steiner tree problemOR Spectrum, 1990
- Fast heuristic algorithms for rectilinear steiner treesAlgorithmica, 1989
- Maximum savings in the Steiner problem in phylogenyJournal of Theoretical Biology, 1984
- AN 0 (N log N) HEURISTIC ALGORITHM FOR THE RECTILINEAR STEINER MINIMAL TREE PROBLEMEngineering Optimization, 1980
- An O ( n log n ) Algorithm for Rectilinear Minimal Spanning TreesJournal of the ACM, 1979
- An O(n log n) algorithm for suboptimal rectilinear Steiner treesIEEE Transactions on Circuits and Systems, 1979
- Use of Steiner's problem in suboptimal routing in rectilinear metricIEEE Transactions on Circuits and Systems, 1976
- Shortest Connection Networks And Some GeneralizationsBell System Technical Journal, 1957
- On the Shortest Spanning Subtree of a Graph and the Traveling Salesman ProblemProceedings of the American Mathematical Society, 1956