Equivalence, Indicators, Quasi-indicators and Optimal Steiner Topologies on Four Points in Space

• Autorzy: Weng J.F. , Smith J.MacGregor , Brazil M. , Thomas D.A.
• Języki publikacji: EN

Abstrakty

EN

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

EN

equivalence; quasi-indicator; Steiner tree

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 84, nr 1
• Strony: 135--149
• Opis fizyczny: bibliogr. 12 poz., tab., wykr.

Twórcy

autor

Weng J.F.

autor

Smith J.MacGregor

autor

Brazil M.

autor

Thomas D.A.

• Department of Electrical and Electronic Engineering, University of Melbourne, 3010 VICTORIA, Australia,

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.