The Steiner tree research at DIKU experiences a revival
Steiner tree, Algorithmics
Early December, DIKU researchers travel to the east coast of the USA to participate in the conference, DIMACS Challenge, and to present their newest results on the Steiner tree problem. Among these are Pawel Winter, who is internationally recognized as a leading expert on geometric Steiner trees. Now, after years of pursuing other research interests, he has returned to this field which started his research career about 30 years ago.
The Steiner tree research group was founded by accident
The Steiner tree problem is about finding the shortest path between a set of points (read more on the right hand side) and has puzzled scientists for over 200 years. The tradition in researching Steiner trees at the Department of Computer Science (DIKU) at University of Copenhagen, however, began only 30 years ago. In fact, research in these NP-hard geometrical problems set off with Pawel Winter, who had gained his curiosity in the subject in a rather peculiar way:
“I was first introduced to the Steiner tree problem when I was about to write my Master's Thesis back in 1980”, Pawel Winter recounts, today a Professor at the Department of Computer Science. “My supervisor, Jakob Krarup, (today professor emeritus, red.) had a piece of paper in his desk drawer with a long list of thesis subjects. He took this list out and asked me to "choose one!” I protested and said that I didn't know the subjects well enough to be able to make an informed choice, but he was quite unconcerned and responded, “That doesn't matter, just point to the paper and choose a subject”. And that is how the Steiner tree problem in its many different facets became one (of more) important subject for my professional career as a scientist”.
After this somewhat shocking experience, Pawel went home and scrutinized the problem. He quickly came to the conclusion that the Steiner tree problem was interesting and that he wanted to go for it. "I was lucky", Pawel chuckles, "I pointed well".
Since then, he has issued the book “The Steiner Tree Problem” (1992) which has gained canonical status on the international scene of Steiner research. At DIKU, the interest in Steiner trees eventually spread to Martin Zachariasen, Pawel's former Ph.D. student, presently professor and Head of Department, who has made the Steiner tree research central to his career as a scientist. Most recently, a DIKU postdoc, Rasmus Fonseca, has turned towards Steiner research.
Together this Steiner tree research trio are joining scientific forces at the DIMACS Challenge workshop in December, to present their latest results: The DIKU team have turned their backs to the two-dimensional Euclidian plane and moved into the far more challenging problem of working with Steiner trees in three and more dimensions - so far, they have succeeded in connecting 18 points in 3D.
Steiner trees have been known since 1811 - today they are used to solve real world problems
The Steiner tree problem was initially formulated in 1811 by the French mathematician and logician Joseph Diaz Gergonne (depicted left). Its name is credited to the Swiss mathematician, Jakob Steiner (1796–1863), which is however somewhat misleading since he never contributed significantly to solving the problem.
It was however not until the 1950s and 60s that the Steiner tree problem became more than a geometrical curiosity. With the opportunity of solving the problem with computers, it became possible to find optimal solutions for very big networks.
It turned out that Steiner trees were suited for solving a number of different practical problems. For instance, in the 50's the American Bell Telephone Company needed to calculate an optimal network connecting its costumers to determine how much each costumer had to pay for their connection.
In recent time, Steiner tree algorithms and heuristics have become so efficient and computers' capacity so great that Steiner trees can be used for practical problems. In 1989, American scientists succeeded in connecting 29 cities by using Steiner trees, but 11 years later Pawel Winter and Martin Zachariasen could present a much more impressive result - a Steiner tree interconnecting no less than 13.509 cities.
Networks of optimal Steiner trees offer a number of applications, especially within logistics and electronics. Apart from using Steiner trees in the construction of communication and infrastructure networks, today it is also common to use Steiner trees for designing the layout of wires in computer chips in order to avoid delays and save energy.
What excites Pawel Winter is not so much the practical application as the interesting theoretical challenges offered by the Steiner tree problem which has kept him engaged during all these years. Nonetheless, he envisages several ways of applying Steiner trees in 3D. For instance, one could imagine the need for connecting satellites in space, platforms on the ocean, or a rectilinear network of water and power cables in houses. As is often the case of this type of application, it is necessary to account for obstacles to be avoided by the network and so the problem becomes even more difficult to solve.
The Steiner tree problem research is as strong as ever
Even though algorithmic scientists have worked with the Steiner tree problemfor many years there is still activity in the field. This is obvious from the well-established biannual DIMACS challenge which focuses on a different algorithmic problem. In previous years well-known algorithmic problems such as the shortest path problem and the traveling salesman problem have been the subject of the challenge, but in 2014 the Steiner tree problem has the central stage.
The Steiner tree explained
The Steiner tree problem is about finding the shortest path between a set of points.
As opposed to minimum spanning trees (figure a) where all paths go through the points themselves, Steiner trees (figures b and c) allow you to insert ekstra mediating points (Steiner points) resulting in a shorter cumulative length. This, however, also makes the problem so much the harder (even NP-complete) since it is difficult to calculate how many extra mediating points there should be and where they should be placed.
Figure a) represents a minimum spanning tree, figure b) is an Euclidian Steiner tree and figure c) is a rectilinear Steiner tree.
A formal definition
If N is a final set of points in the plane, the Euclidian Steiner tree problem is: Find a set of line segments so that all the points are connected with each other and so that the total Euclidian length of the line segments is minimized.
Read more about Steiner trees
Read the introductory paper, "The Shortest-Network Problem" (1989), in Scientific American about the Steiner tree problem.
Read also the recent paper on the history of the Steiner tree problem by Martin Zachariasen et al., "On the history of the Euclidean Steiner tree problem" (2014), in Archive for History of Exact Sciences.