About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SODA 1995
Conference paper
Finding subsets maximizing minimum structures
Abstract
We are interested in 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.1' In particular, we are interested in three problems of this type, where the structure to be minimized is a Spanning Tree (Remote-MST), Steiner Tree (remoteST), or Traveling Salesperson tour (Remote-TSP). We give: (1) iVP-hardness and lower bounds of approximation ratios of the above remote fe-set problems, (2) a tight performance ratio of 4 for a greedy algorithm for Remote-MST on metric graphs, (3) au improved approximation algorithm for Remote-MST with a performance ratio 2.25 for a graph induced from Euclidean distances of a set of points in a plane, and (4) corresponding results for Remote-ST and Remote-TSP problems.