Affiliations: Department of Electrical and Electronic Engineering,
The University of Melbourne, Victoria 3010, Australia.
E-mail: [email protected] | Department of Mechanical and Industrial Engineering,
University of Massachusetts, Amherst, MA 01003, USA
Abstract: 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 E^3 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
quasiindicators. 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.
Keywords: equivalence, quasi-indicator, Steiner tree
