return

Celebratio Mathematica

J. Hyam Rubinstein

Topology

Hyam Rubinstein and optimal networks

Doreen Thomas

For over 20 years, Hyam Ru­bin­stein has made a ma­jor con­tri­bu­tion to the area of net­work op­tim­isa­tion, start­ing with im­port­ant con­tri­bu­tions to the clas­sic­al Eu­c­lidean Stein­er tree prob­lem. This prob­lem is to find the shortest net­work (tree) \( T \) con­nect­ing a giv­en set \( X \) of \( n \) points in the plane. Ad­di­tion­al points, called Stein­er points, can be ad­ded to find the solu­tion. The fig­ure be­low shows the Stein­er tree on three points, \( A \), \( B \) and \( C \) with an ad­di­tion­al Stein­er point \( S \).

Ap­plic­a­tions of this prob­lem have been the lay­out of tele­phone net­works, pipelines and road­way net­works, and the rec­ti­lin­ear ver­sion has been ap­plied to the design of elec­tron­ic cir­cuits on VLSI (very large scale in­teg­rated) chips. Al­though there is a fi­nite al­gorithm (Melzak’s Al­gorithm) to find \( T \), the prob­lem has been shown to be NP-com­plete. On the oth­er hand, the min­im­al span­ning tree on \( X \), where no ad­di­tion­al points are ad­ded, can be found in poly­no­mi­al time. In the 1980s, math­em­aticians E. N. Gil­bert and H. O. Pol­lak from Bell Labor­at­or­ies, con­jec­tured that the ra­tio of the Stein­er tree to the min­im­um span­ning tree is at least \( \sqrt 3/2 \), that is the Stein­er tree’s length is at most about 13.4% short­er than the min­im­al span­ning tree’s length. The ra­tio of \( \sqrt 3/2 \) oc­curs in the simple ex­ample where there are three giv­en points form­ing an equi­lat­er­al tri­angle. Em­in­ent math­em­aticians such as F. K. Hwang and R. L. Gra­ham who were work­ing at AT&T Bell Labs were in­ter­ested in this prob­lem, where the ap­plic­a­tion was to private line tar­iffs.

In 1990, Hyam Ru­bin­stein re­viewed a pa­per on the ra­tio con­jec­ture for 5 points and he real­ised that the vari­ation­al tech­niques that he used in his work on min­im­al sur­faces could be ap­plied to the Stein­er net­work prob­lem. Hyam had re­cently kindly agreed to work with Doreen Thomas, who had been awar­ded a Re-entry Re­search Fel­low­ship at The Uni­versity of Mel­bourne to en­cour­age wo­men to re­turn to aca­demia. This led to Hyam do­ing re­search on op­tim­al net­works for the next two dec­ades, and to his body of work, from solu­tions to long- stand­ing fun­da­ment­al prob­lems (such as the Stein­er ra­tio con­jec­ture) to suc­cess­ful col­lab­or­a­tions with the min­ing in­dustry in­ter­na­tion­ally, design­ing un­der­ground mine ac­cess net­works.

The vari­ation­al tech­nique proved to be a cru­cial tool for at­tack­ing the Stein­er ra­tio con­jec­ture. Two prin­cip­al reas­ons were these:

  1. If you have a Stein­er tree and move a giv­en ver­tex along it, the length of the cor­res­pond­ing min­im­um span­ning tree (without Stein­er points) changes in a way which is very eas­ily com­puted. Oth­er mo­tions of a ver­tex also lead to easy con­trol of the way in which the Stein­er ra­tio changes.

  2. In the pro­cess of min­im­ising the ra­tio, one ends up with a mul­ti­pli­city of min­im­um span­ning trees with many line seg­ments of equal length. The set of all these edges in these trees is a very nice ob­ject to work with.

This tech­nique was used by Hyam and Doreen to prove the Stein­er ra­tio con­jec­ture holds for con­fig­ur­a­tions of six points, and fur­ther to show that if \( n \) giv­en points lie on a circle, then the Stein­er ra­tio con­jec­ture also holds. In 1991, D. Z. Du and F. K. Hwang pub­lished a solu­tion to the Stein­er ra­tio con­jec­ture us­ing this con­fig­ur­a­tion space ap­proach but with con­vex­ity as their main idea. However prob­lems have been found with their proof, and the gen­er­al Stein­er ra­tio con­jec­ture re­mains an open prob­lem.

After a term as Head of the De­part­ment of Math­em­at­ics at The Uni­versity of Mel­bourne, Hyam took a well-de­served sab­bat­ic­al at the In­sti­tute for Ad­vanced Study, Prin­ceton. Here he tackled an­oth­er open prob­lem, R. L. Gra­ham’s prob­lem on shortest net­works for points on a circle. Sup­pose a con­fig­ur­a­tion \( X \) con­sists of \( n \) points ly­ing on a circle of ra­di­us \( r \). If at most one of the edges join­ing neigh­bour­ing points has length strictly great­er than \( r \), then the Stein­er tree \( T \) con­sists of all these edges with a longest edge re­moved. In or­der to show that \( T \) is the min­im­al span­ning tree \( M \), a vari­ation­al ap­proach was used to show the Stein­er ra­tio for this con­fig­ur­a­tion is at least one, and equals one if and only if \( T \) and \( M \) co­in­cide. The vari­ation­al ap­proach greatly re­duced the num­ber of pos­sible Stein­er trees (dif­fer­ent to­po­lo­gies) that needed to be con­sidered. To­geth­er with a stu­dent, Tony Cole, Hyam went on to gen­er­al­ise this res­ult to con­vex con­fig­ur­a­tions with ra­di­us of max­im­um curvature \( r \).

By 1996, Nick Wormald had joined the net­work-op­tim­isa­tion team. In a pa­per which provides in­sight in­to a bound­ary between an NP-hard Stein­er prob­lem and one that is poly­no­mi­ally solv­able, Hyam and his col­leagues gave a poly­no­mi­al-time al­gorithm for solv­ing the Eu­c­lidean Stein­er tree prob­lem when the ter­min­als are con­strained to lie on a fixed set of dis­joint fi­nite-length com­pact simple smooth curves. It was also shown that the prob­lem is NP-hard if the ter­min­als lie on two par­al­lel in­fin­ite lines, or on a bent line seg­ment, provided the bend has an angle of less than 120 de­grees. In a re­lated pa­per, it was shown that there is a poly­no­mi­al al­gorithm for the trav­el­ing sales­man when the towns to be vis­ited are con­strained to lie on “smooth” roads.

In 1986, Mar­tin Gard­ner wrote an art­icle in Sci­entif­ic Amer­ic­an where he con­jec­tured that the min­im­al Stein­er tree join­ing the 81 points at the corners of a check­er­board could be con­struc­ted by join­ing many rep­licas of the Stein­er tree on the 4 points at the corners of a square. This Stein­er tree has two Stein­er points, and we will call it an “\( X \)” for reas­ons which are ob­vi­ous from the fig­ure be­low that shows a Stein­er tree on four points, \( A \), \( B \), \( C \) and \( D \) with 2 Stein­er points \( S1 \) and \( S2 \).

F. Chung and R. Gra­ham had res­ults on Stein­er trees for \( 2{\times}n \) rect­an­gu­lar ar­rays (lad­ders), but were un­able to solve the gen­er­al prob­lem, though they gave some con­jec­tured solu­tions to the \( n{\times}n \) prob­lem. To­geth­er with Nick, Doreen and two new mem­bers of the net­work-op­tim­isa­tion team, Jia Weng and Mar­cus Brazil, Hyam pub­lished three sem­in­al pa­pers on \( m{\times}n \) ar­rays and more gen­er­al lat­tice sets. The first pa­per answered the con­jec­ture, show­ing that each full com­pon­ent (where each ver­tex is of de­gree one; the smal­lest ir­re­du­cible blocks from which the Stein­er tree is com­posed) is in­deed the min­im­al Stein­er tree for the ver­tices of a square if and only if \( m=n= 2k \). This was gen­er­al­ised to square or rect­an­gu­lar ar­rays of in­teger lat­tice points where small com­pon­ents oth­er than \( X \)s were needed. In some sense an \( X \) is the most ef­fi­cient com­pon­ent but, when \( n \) is oth­er than \( 2k \), oth­er com­pon­ents with “ex­cess” length are needed. Mar­tin Gard­ner, in the book “The Last Re­cre­ations: Hy­dras, Eggs and Oth­er Mys­ti­fic­a­tions”, de­scribed the solu­tion to the Stein­er ra­tio con­jec­ture as well as the solu­tion to the check­er­board prob­lem as “the two most im­port­ant con­tri­bu­tions to the Stein­er prob­lem in the dec­ade”.

In 2000, Dav­id Lee, from the Uni­versity of South Aus­tralia, sug­ges­ted to the net­work-op­tim­isa­tion team that they should ap­ply their re­search to the design of the ac­cess net­work in un­der­ground mines. The ac­cess net­work in an un­der­ground mine, such as a gold or cop­per mine, is made up of a net­work of tun­nels and shafts used to ac­cess the ore as well as to haul the ore back to the sur­face. The net­work of tun­nels links fixed ac­cess points which are giv­en by the min­ing en­gin­eers with a sur­face portal. The tun­nels are gradi­ent- and curvature-con­strained due to the large haulage vehicles. Typ­ic­ally the gradi­ent is 1:7 and the ra­di­us of curvature is around 25 meters. Hyam, to­geth­er with his col­leagues de­veloped the fun­da­ment­al the­ory of 3-di­men­sion­al gradi­ent-con­strained net­works which are used to mod­el un­der­ground mines at a stra­tegic level. In ad­di­tion, the the­ory de­veloped by Lester Du­bins (so-called Du­bins paths, which gives the shortest curvature-con­strained path in the plane join­ing two dir­ec­ted points) was ex­ten­ded to gradi­ent-con­strained paths in 3-di­men­sion­al space. The the­ory un­der­lies al­gorithms de­veloped to de­term­ine min­im­um-cost curvature and gradi­ent-con­strained net­works in 3 di­men­sions, where the min­im­um cost in­cludes both the de­vel­op­ment costs and the haulage costs over the life of the mine.

Peter Gross­man was ap­poin­ted to work with the team on the min­ing prob­lem, and write the code to im­ple­ment the al­gorithms that design the min­ing net­works. Hyam and his col­leagues de­veloped three soft­ware tools: UNO (Un­der­ground Net­work Op­tim­iser), which gives the best to­po­logy link­ing points in three-di­men­sion­al space with a gradi­ent-con­strained net­work; DOT (De­cline Op­tim­isa­tion Tool), which gives a gradi­ent- and curvature-con­strained path link­ing ac­cess points on vari­ous equally spaced levels un­der­ground; and PUNO (Planar Un­der­ground Net­work Op­tim­iser) which gives net­works, Stein­er trees, and link­ing points on a min­ing level. For three years from 2008, Hyam led a large in­dustry pro­ject through AMIRA (an as­so­ci­ation of min­ing com­pan­ies that spon­sors re­search pro­jects) to de­vel­op the soft­ware to a com­mer­cial level. The fol­low­ing com­pan­ies have sponsored the soft­ware de­vel­op­ment and re­search on this prob­lem: New­mont Aus­tralia Lim­ited, Rio Tinto, Oz Min­er­als, BHP Bil­liton, Bar­ri­ck Gold, Vale Inco, Xstrata, Rand and Tribune.

Hyam’s con­tri­bu­tion to fun­da­ment­al re­search on Stein­er tree prob­lems and more gen­er­al net­work op­tim­isa­tion prob­lems, as well as the min­ing ap­plic­a­tion, has been pro­found. His lead­er­ship and ded­ic­a­tion to this work and his abil­ity to con­tinu­ally find fund­ing for the pro­ject over more than twenty years has been re­mark­able. The net­work-op­tim­isa­tion team is so for­tu­nate to be able to work with Hyam and we look for­ward to the next twenty years.