The Steiner problem: A survey

In the last decade the Steiner problem has attracted considerable attention from investigators in the field of discrete optimization. Here we give a brief survey of the fundamental results concerning the properties and algorithms for solving the Steiner problem on a Euclidean plane, the Steiner problem on a plane with a rectangular metric, and the Steiner problem on graphs, and in the latter problem we focus on results obtained after 1985. We consider both exact and heuristic algorithms, their efficiency and the results of numerical experiments. We give examples of probabilistic approaches to the solution of the problem. The final section of the paper is devoted to the Gilbert – Pollak conjecture.