A High Performance Approximate Algorithm for the Steiner Problem in Graphs

A new approximate algorithm (GBA) for the Steiner problem in graphs (SPG) based on an iterative execution of a previous heuristic to the problem (SPH) is presented. GBA looks for a subset of vertices which, used as terminals, can produce a near-optimal solution. In addition, the tree associated to each of these subsets is selected at random. The worst-case time complexity of the algorithm is O(|V|3) and the cost of the solution is guaranteed to be less than twice the optimal. GBA is tested on classical benchmark problems and its performance compares favorably to that of some of the best existing SPG approaches with respect both to solution quality and specially runtime.