Doreen Thomas
For over 20 years, Hyam Rubinstein has made a major contribution to the area of network optimisation, starting with important contributions to the classical Euclidean Steiner tree problem. This problem is to find the shortest network (tree) \( T \) connecting a given set \( X \) of \( n \) points in the plane. Additional points, called Steiner points, can be added to find the solution. The figure below shows the Steiner tree on three points, \( A \), \( B \) and \( C \) with an additional Steiner point \( S \).
Applications of this problem have been the layout of telephone networks, pipelines and roadway networks, and the rectilinear version has been applied to the design of electronic circuits on VLSI (very large scale integrated) chips. Although there is a finite algorithm (Melzak’s Algorithm) to find \( T \), the problem has been shown to be NP-complete. On the other hand, the minimal spanning tree on \( X \), where no additional points are added, can be found in polynomial time. In the 1980s, mathematicians E. N. Gilbert and H. O. Pollak from Bell Laboratories, conjectured that the ratio of the Steiner tree to the minimum spanning tree is at least \( \sqrt 3/2 \), that is the Steiner tree’s length is at most about 13.4% shorter than the minimal spanning tree’s length. The ratio of \( \sqrt 3/2 \) occurs in the simple example where there are three given points forming an equilateral triangle. Eminent mathematicians such as F. K. Hwang and R. L. Graham who were working at AT&T Bell Labs were interested in this problem, where the application was to private line tariffs.
In 1990, Hyam Rubinstein reviewed a paper on the ratio conjecture for 5 points and he realised that the variational techniques that he used in his work on minimal surfaces could be applied to the Steiner network problem. Hyam had recently kindly agreed to work with Doreen Thomas, who had been awarded a Re-entry Research Fellowship at The University of Melbourne to encourage women to return to academia. This led to Hyam doing research on optimal networks for the next two decades, and to his body of work, from solutions to long- standing fundamental problems (such as the Steiner ratio conjecture) to successful collaborations with the mining industry internationally, designing underground mine access networks.
The variational technique proved to be a crucial tool for attacking the Steiner ratio conjecture. Two principal reasons were these:
If you have a Steiner tree and move a given vertex along it, the length of the corresponding minimum spanning tree (without Steiner points) changes in a way which is very easily computed. Other motions of a vertex also lead to easy control of the way in which the Steiner ratio changes.
In the process of minimising the ratio, one ends up with a multiplicity of minimum spanning trees with many line segments of equal length. The set of all these edges in these trees is a very nice object to work with.
This technique was used by Hyam and Doreen to prove the Steiner ratio conjecture holds for configurations of six points, and further to show that if \( n \) given points lie on a circle, then the Steiner ratio conjecture also holds. In 1991, D. Z. Du and F. K. Hwang published a solution to the Steiner ratio conjecture using this configuration space approach but with convexity as their main idea. However problems have been found with their proof, and the general Steiner ratio conjecture remains an open problem.
After a term as Head of the Department of Mathematics at The University of Melbourne, Hyam took a well-deserved sabbatical at the Institute for Advanced Study, Princeton. Here he tackled another open problem, R. L. Graham’s problem on shortest networks for points on a circle. Suppose a configuration \( X \) consists of \( n \) points lying on a circle of radius \( r \). If at most one of the edges joining neighbouring points has length strictly greater than \( r \), then the Steiner tree \( T \) consists of all these edges with a longest edge removed. In order to show that \( T \) is the minimal spanning tree \( M \), a variational approach was used to show the Steiner ratio for this configuration is at least one, and equals one if and only if \( T \) and \( M \) coincide. The variational approach greatly reduced the number of possible Steiner trees (different topologies) that needed to be considered. Together with a student, Tony Cole, Hyam went on to generalise this result to convex configurations with radius of maximum curvature \( r \).
By 1996, Nick Wormald had joined the network-optimisation team. In a paper which provides insight into a boundary between an NP-hard Steiner problem and one that is polynomially solvable, Hyam and his colleagues gave a polynomial-time algorithm for solving the Euclidean Steiner tree problem when the terminals are constrained to lie on a fixed set of disjoint finite-length compact simple smooth curves. It was also shown that the problem is NP-hard if the terminals lie on two parallel infinite lines, or on a bent line segment, provided the bend has an angle of less than 120 degrees. In a related paper, it was shown that there is a polynomial algorithm for the traveling salesman when the towns to be visited are constrained to lie on “smooth” roads.
In 1986, Martin Gardner wrote an article in Scientific American where he conjectured that the minimal Steiner tree joining the 81 points at the corners of a checkerboard could be constructed by joining many replicas of the Steiner tree on the 4 points at the corners of a square. This Steiner tree has two Steiner points, and we will call it an “\( X \)” for reasons which are obvious from the figure below that shows a Steiner tree on four points, \( A \), \( B \), \( C \) and \( D \) with 2 Steiner points \( S1 \) and \( S2 \).
F. Chung and R. Graham had results on Steiner trees for \( 2{\times}n \) rectangular arrays (ladders), but were unable to solve the general problem, though they gave some conjectured solutions to the \( n{\times}n \) problem. Together with Nick, Doreen and two new members of the network-optimisation team, Jia Weng and Marcus Brazil, Hyam published three seminal papers on \( m{\times}n \) arrays and more general lattice sets. The first paper answered the conjecture, showing that each full component (where each vertex is of degree one; the smallest irreducible blocks from which the Steiner tree is composed) is indeed the minimal Steiner tree for the vertices of a square if and only if \( m=n= 2k \). This was generalised to square or rectangular arrays of integer lattice points where small components other than \( X \)s were needed. In some sense an \( X \) is the most efficient component but, when \( n \) is other than \( 2k \), other components with “excess” length are needed. Martin Gardner, in the book “The Last Recreations: Hydras, Eggs and Other Mystifications”, described the solution to the Steiner ratio conjecture as well as the solution to the checkerboard problem as “the two most important contributions to the Steiner problem in the decade”.
In 2000, David Lee, from the University of South Australia, suggested to the network-optimisation team that they should apply their research to the design of the access network in underground mines. The access network in an underground mine, such as a gold or copper mine, is made up of a network of tunnels and shafts used to access the ore as well as to haul the ore back to the surface. The network of tunnels links fixed access points which are given by the mining engineers with a surface portal. The tunnels are gradient- and curvature-constrained due to the large haulage vehicles. Typically the gradient is 1:7 and the radius of curvature is around 25 meters. Hyam, together with his colleagues developed the fundamental theory of 3-dimensional gradient-constrained networks which are used to model underground mines at a strategic level. In addition, the theory developed by Lester Dubins (so-called Dubins paths, which gives the shortest curvature-constrained path in the plane joining two directed points) was extended to gradient-constrained paths in 3-dimensional space. The theory underlies algorithms developed to determine minimum-cost curvature and gradient-constrained networks in 3 dimensions, where the minimum cost includes both the development costs and the haulage costs over the life of the mine.
Peter Grossman was appointed to work with the team on the mining problem, and write the code to implement the algorithms that design the mining networks. Hyam and his colleagues developed three software tools: UNO (Underground Network Optimiser), which gives the best topology linking points in three-dimensional space with a gradient-constrained network; DOT (Decline Optimisation Tool), which gives a gradient- and curvature-constrained path linking access points on various equally spaced levels underground; and PUNO (Planar Underground Network Optimiser) which gives networks, Steiner trees, and linking points on a mining level. For three years from 2008, Hyam led a large industry project through AMIRA (an association of mining companies that sponsors research projects) to develop the software to a commercial level. The following companies have sponsored the software development and research on this problem: Newmont Australia Limited, Rio Tinto, Oz Minerals, BHP Billiton, Barrick Gold, Vale Inco, Xstrata, Rand and Tribune.
Hyam’s contribution to fundamental research on Steiner tree problems and more general network optimisation problems, as well as the mining application, has been profound. His leadership and dedication to this work and his ability to continually find funding for the project over more than twenty years has been remarkable. The network-optimisation team is so fortunate to be able to work with Hyam and we look forward to the next twenty years.
