In particular, we are interested in three problems of this type, where the structure to be minimized is a Spanning Tree (RMST), Steiner Tree (RST), or Traveling Salesperson tour (RTSP).
We give a natural greedy approximation algorithm that simultaneously approximates all three problems on metric graphs. For instance, its performance ratio for RMST is exactly 4, while it is NP-hard to approximate within a factor of less than 2. We also show a better approximation for graphs induced by Euclidean points in the plane, give an exact algorithm for graphs whose distances correspond to shortest-path distances in a tree, and give hardness and approximability results for general non-metric graphs.