Efficient greedy heuristics for Steiner Tree problems using reoptimization and supermodularity

The optimum Steiner Tree problem in a (nondirected) graph is known to belong to the class of NP-hard problems. However large scale instances (typically hundreds or thousands of nodes) arise in such important applications as optimal communication network design, of VLSI routing. There is therefore a strong need for efficient heuristics. This paper discusses efficient implementations of greedy-type procedures for approximate solution of symmetric Steiner Tree problems with arbitrary nonnegative lengths on the edges. A special subclass of problems (meeting the so-called ‘nonadjacency condition’) is also introduced and studied. Various ways of improving the computational efficiency of the basic greedy algorithm are examined, among which the use of reoptimization procedures and proper exploitation of a supermodularity property of an associated set function; thanks to the latter the total number of minimum spanning tree computations can be significantly reduced according to Minoux’ ‘accelerated greedy algorithm’ principle and lower bounds can be derived (thus providing estimates of the quality of the approximate solutions obtained).