A PTAS for the metric case of the optimum weighted source-destination communication spanning tree problem (Q2632008)

The paper presents a polynomial-time approximation scheme for the metric case (edge-length satisfying the triangle inequality) of the optimum weighted source-destination communication spanning tree problem (WSDOCT). As this is mainly a theoretical result due to unpractical PTAS complexity, the authors also present an \(O(n^2\log n+mn)\) 2-approximation for the problem which improves the time complexity required by the PTAS to achieve the same 2-approximation. The WSDOCT optimization problem is formally defined as follows: Given an undirected graph \(G = (V, E)\) with non-negative lengths \(\omega(e)\) associated to the edges and non-negative weights \(\sigma(u)\) and \(\rho(u)\) of nodes \(u\in V\), the objective is to find a spanning tree \(T\) of \(G\) that minimizes: \[ \sum\limits_{u,v\in V}(\sigma(u)\rho(v)+ \rho(u)\sigma(v))d(T, u, v), \] where \(d(H, x, y)\) is the minimum distance between nodes \(x\) and \(y\) in a graph \(H\subseteq G\).