Paper by Erik D. Demaine

Reference:

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.

Abstract:

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.

Comments:

This paper is also available from SpringerLink.

Copyright:

Copyright held by the authors.

Length:

The paper is 12 pages.

Availability:

The paper is available in PostScript (305k), gzipped PostScript (140k), and PDF (172k).

See information on file formats.

[Google Scholar search]