A 2-approximation algorithm and beyond for the minimum diameter k-Steiner forest problem

Given an edge-weighted undirected graph G = ( V, E, w ) and a subset T ⊆ V of p terminals, a k-Steiner forest spanning all the terminals in T includes k branches, where every branch is a Steiner tree. The diameter of a k-Steiner forest is referred to as the maximum distance between two terminals of a branch. This paper studies the minimum diameter k-Steiner forest problem (MDkSFP) and establishes the relationship between MDkSFP and the absolute k-Steiner center problem (AkSCP). We first obtain a 2-factor dual approximation algorithm for AkSCP, and then achieve a 2-approximation algorithm for MDkSFP based on the 2-approximation to AkSCP. Furthermore, we develop an improved 2ρ-approximation algorithm for MDkSFP, where ρ < 1 in general, by perturbing the sites of facilities and re-clustering the terminals.

Authors

• Wei Ding
• Ke Qiu

Keywords

• k-Steiner forest
• Diameter
• Perturbation