Abstract
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).
| Original language | English |
|---|---|
| Pages (from-to) | 147-155 |
| Number of pages | 9 |
| Journal | Networks |
| Volume | 36 |
| Issue number | 3 |
| DOIs | |
| State | Published - Oct 2000 |
Keywords
- Approximation algorithms
- Covering problems
- Graph diameter
- NP-complete
Fingerprint
Dive into the research topics of 'Minimum-diameter covering problems'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver