## 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.