The hardness and approximation of the star p-hub center problem

We consider the star p-hub center problem recently introduced by Yaman and Elloumi [H. Yaman and S. Elloumi. Star p-hub center problem and star p-hub median problem with bounded path lengths, Comput. Oper. Res., 39 (11) (2012) 2725-2732]. We first show that the problem does not admit a (1.25−ϵ)-approximation algorithm for any ϵ>0 unless P=NP. In particular this gives the first strong NP-hardness result for the problem in a metric space. We also present, complementing the inapproximability result, a purely combinatorial 3.5-approximation algorithm for the star p-hub center problem.