Premium
Minimum‐diameter covering problems
Author(s) -
Arkin Esther M.,
Hassin Refael
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/1097-0037(200010)36:3<147::aid-net1>3.0.co;2-m
Subject(s) - cover (algebra) , mathematics , combinatorics , set cover problem , minimum distance , set (abstract data type) , time complexity , discrete mathematics , algorithm , mathematical optimization , computer science , mechanical engineering , engineering , programming language
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. The 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 these basic problems, and we prove in other cases that no such algorithms exist (assuming P ≠ NP ). © 2000 John Wiley & Sons, Inc.