Finding subsets maximizing minimum structures

Abstract: We consider the problem of finding a set of k vertices in a graph that are in some sense remote, stated more formally: ``Given a graph G and an integer k, find a set P of k vertices for which the total weight of a minimum structure on P is maximized.''

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.