Paper by Erik D. Demaine
- Erik D. Demaine and Morteza Zadimoghaddam, “Minimizing the Diameter of a Network using Shortcut Edges”, in Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), Lecture Notes in Computer Science, volume 6139, Bergen, Norway, June 21–23, 2010, pages 420–431.
We study the problem of minimizing the diameter of a graph by adding k
shortcut edges, for speeding up communication in an existing network design.
We develop constant-factor approximation algorithms for different variations
of this problem. We also show how to improve the approximation ratios using
resource augmentation to allow more than k shortcut edges. We observe
a close relation between the single-source version of the problem, where we
want to minimize the largest distance from a given source vertex, and the
well-known k-median problem. First we show that our constant-factor
approximation algorithms for the general case solve the single-source problem
within a constant factor. Then, using a linear-programming formulation for
the single-source version, we find a (1 + ε)-approximation
using O(k log n) shortcut edges. To show the
tightness of our result, we prove that any
(3/2 − ε)-approximation for the single-source version
must use Ω(k log n) shortcut edges assuming
P ≠ NP.
- This paper is also available from SpringerLink.
- Copyright held by the authors.
- The paper is 12 pages.
- The paper is available in PostScript (305k), gzipped PostScript (140k), and PDF (172k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated February 24, 2021 by