Warianty tytułu
Języki publikacji
Abstrakty
The Steiner tree problem is an intractable optimization problem, which asks for a network, in fact a tree, interconnecting a given point set V in a metric space and minimizing the total length of the network. The tree topology t of the network is called a Steiner topology and a tree T with minimum length with respect to its Steiner topology is called a Steiner tree. As a combinatorial optimization problem, the Steiner tree problem asks for a Steiner tree T with minimum length over all possible topologies t on V. It has been proved that if T is in E3 then the length of T cannot be expressed by radicals even when T spans just 4 points. For such optimization problems in which the objective functions do not have closed form solutions the traditional approach is approximation. In this paper we propose a new approach by introducing some new concepts: equivalence, indicators and quasi-indicators, and then we apply these concepts to the Steiner tree problem. Roughly speaking, a quasi-indicator is a function that is simple to compute but indicates with high probability the optimal solution to the original optimisation problem. For a specific optimisation problem - finding the optimal Steiner topologies on 4 points in space, we demonstrate how to find good quasi-indicators. The extensive computational experiments over 5000 random 4-point sets show that the best quasi-indicator for finding optimal Steiner topologies on 4 points in space is not only easy to compute but also extremely successful with less than 1.5% failures in indicating optimal topologies even if degeneracy of Steiner minimal trees exists. Moreover, within the 1.5% cases of failure, the maximum and the average relative error are 1.5% and 0.2% respectively. Therefore, the performance of the proposed Q-indicator is very good and could be applied to the four vertices surrounding any pair of adjacent Steiner points in a Steiner tree on n ( > 4) points in space to make local improvements to the topology of the Steiner minimal tree in space.
Słowa kluczowe
Czasopismo
Rocznik
Tom
Strony
135-149
Opis fizyczny
bibliogr. 12 poz., tab., wykr.
Twórcy
autor
autor
autor
autor
- Department of Electrical and Electronic Engineering, University of Melbourne, 3010 VICTORIA, Australia, weng@ee.unimelb.edu.au
Bibliografia
- [1] Dorn W. S.: A duality theorem for convex programs, IBM J. Res. Develop., 4, 1960, 407-413.
- [2] Hwang F. K.: Richards D. S. and WinterP. P.: The Steiner tree problem, Annals of Discrete Mathematics, 53, Elsevier, Amsterdam, 1992.
- [3] Melzak Z. A.: On the problem of Steiner, Canan. Math. Bull., 4, 1961, 143-148.
- [4] Ollerenshaw K.: Minimum networks linking four points in a plane, Inst. Math. Appl., 15, 1978, 208-211.
- [5] Pollak H. O.: Some remarks on the Steiner problem, J. Comb. Theory, Ser. A, 24, 1978, , 278-295.
- [6] Rubinstein J. H., Thomas D. A. and Weng J. F.: Minimum networks for four points in space, Geometriae Dedicata, 93, 2002, 57-70.
- [7] Smith J. MacGregor: Steiner Minimal Trees in 3-d: Theory, Algorithms, and Applications, in The Handbook of Combinatorial Optimization, Kluwer Academic Publishers, Boston, 1998.
- [8] Stanton C. and Smith J. MacGregor: Steiner Trees and 3-DMacromolecular Conformation, INFORMS Journal of Computing,16, 2004, , 470-485.
- [9] Warme D.,Winter D. P. and ZachariasenM.: Exact Algorithms for Plane Steiner Tree Problems: A Comnputational Study, in Advances in Steiner Trees, eds. Du, Smith and Rubinstein, Kluwer Academic Publishers, Boston, 2000.
- [10] Smith W. D.: How To Find Minimal Trees in Euclidean d-space, Algorithmica, 7, 1992, 137-177.
- [11] Smith W. D. and Smith J. MacGregor: On the Steiner ratio in 3-space. Journal of Combinatorial Theory, Series A, 69, 1995, 301-332.
- [12] Weng J. F.: Generalized Steiner problemand hexagonal coordinate system, ActaMath. Appli. Sinica, 8, 1985, 383-397.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS5-0015-0068