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 subset of 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 rho-approximation algorithm for MDkSFP, where rho < 1 in general, by perturbing the sites of facilities and re-clustering the terminals. (C) 2019 Elsevier B.V. All rights reserved.