TY - JOUR

T1 - Finding subsets maximizing minimum structures

AU - Halldórsson, Magnús M.

AU - Iwano, Kazuo

AU - Katoh, Naoki

AU - Tokuyama, Takeshi

N1 - Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

PY - 1999/9

Y1 - 1999/9

N2 - 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 (REMOTE-MST), Steiner tree, or traveling salesperson tour. We study a natural greedy algorithm that simultaneously approximates all three problems on metric graphs. For instance, its performance ratio for REMOTE-MST is exactly 4, while this problem is N P-hard to approximate within a factor of less than 2. We also give a better approximation for graphs induced by Euclidean points in the plane, present an exact algorithm for graphs whose distances correspond to shortest-path distances in a tree, and prove hardness and approximability results for general graphs.

AB - 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 (REMOTE-MST), Steiner tree, or traveling salesperson tour. We study a natural greedy algorithm that simultaneously approximates all three problems on metric graphs. For instance, its performance ratio for REMOTE-MST is exactly 4, while this problem is N P-hard to approximate within a factor of less than 2. We also give a better approximation for graphs induced by Euclidean points in the plane, present an exact algorithm for graphs whose distances correspond to shortest-path distances in a tree, and prove hardness and approximability results for general graphs.

KW - Dispersion

KW - Minimum spanning tree

KW - Steiner tree

KW - Traveling salesperson tour

UR - http://www.scopus.com/inward/record.url?scp=0346443491&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0346443491&partnerID=8YFLogxK

U2 - 10.1137/S0895480196309791

DO - 10.1137/S0895480196309791

M3 - Article

AN - SCOPUS:0346443491

SN - 0895-4801

VL - 12

SP - 342

EP - 359

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 3

ER -