文摘
Given a metric graph \(G=(V, E, w)\) and a center \(c\in V\), and an integer k, the Star k-Hub Center Problem is to find a depth-2 spanning tree T of G rooted by c such that c has exactly k children and the diameter of T is minimized. Those children of c in T are called hubs. The Star k-Hub Center Problem is NP-hard. (Liang, Operations Research Letters, 2013) proved that for any \(\epsilon >0\), it is NP-hard to approximate the Star k-Hub Center Problem to within a ratio \(1.25-\epsilon \). In the same paper, a 3.5-approximation algorithm was given for the Star k-Hub Center Problem. In this paper, we show that for any \(\epsilon > 0\), to approximate the Star k-Hub Center Problem to a ratio \(1.5 - \epsilon \) is NP-hard. Moreover, we give 2-approximation and \(\frac{5}{3}\)-approximation algorithms for the same problem.