The Shared Broadcast Tree Problem and MST

The shared broadcast tree (SBT) problem in Euclidean graphs resembles the minimum spanning tree (MST) problem, but differs from MST in the definition of the objective function. The SBT problem is known to be NP-hard. In the current work, we analyse how closely the MST-solution approximates the SBT-solution, and we prove in particular that the approximation ratio is at least 6. Further, we conduct numerical experiments comparing the MST-solution and the optimum. The results show that the cost of the MST-solution is around 20% higher than the optimal cost.