The Client-Server 2-Spanner Problem and Applications to Network Design
M. Elkin, Dori Peleg · SIROCCO · 1999
This paper studies the client-server version of the 2-spanner problem. This is a natural generalization of the sparse 2-spanner problem that turns out to be useful for certain network design problems. The paper presents a logarithmic ratio approximation algorithm for this problem. The algorithm and the analysis are extended to the directed client-server 2-spanner problem and to the client-server augmentation 2-spanner problem, establishing a logarithmic approximation ratio for these problems too. The paper also studies the bounded-diameter network design (BDND) problem, and establishes a logarithmic approximation ratio for the problem, using the tools developed for the client-server 2-spanner problem.