Minimum-diameter covering problems

A set V and a collection of (possibly nondisjoint) subsets are given. Also given is a real matrix describing distances between elements of V. A cover is a subset of V containing at least one representative from each subset. T he multiple-choice minimum-diameter problem is to select a cover of minimum diameter. The diameter is defined as the maximum distance between any pair of elements in the cover. The multiple-choice dispersion problem, which is closely related, asks us to maximize the minimum distance between any pair of elements in the cover. The problems are NP-hard. We present polynomial time algorithms for approximating special cases and generalizations of thes e basic problems, and we prove in other cases that no such algorithms exist (assuming P not equal NP). (C) 2000 John Wiley & Sons, Inc.