A complete weighted graph G = (V, E, w) is called ∆_β-metric, for some β ≥ 1/2, if G satisfies the β-triangle inequality, i.e., w(u, v) ≤ β. (w(u, x) + w(x, v)) for all vertices u,v, x ∈ V. Given a ∆_β-metric graph G = (V,E,w) and a center c ∈ V, and an integer p, the ∆_β-Star p-Hub Center Problem (∆_β-SpHCP) is to find a depth-2 spanning tree T of G rooted at c such that c has exactly p children and the diameter of T is minimized. The children of c in T are called hubs. For β=1, ∆_β-SpKCP is NP-hard. (Chen et al, COCOON 2016) proved that for any ε > 0, it is NP-hard to approximate the ∆_β-SpHCP to within a ratio 1.5 - ε for β = 1. In the same paper, a 5/3-approximation algorithm was given for ∆_β-SpHCP for β = 1. In this paper, we study ∆_β-SpHCP for all β ≥ 1/2. We show that for any ε > 0, to approximate the ∆_β-SpHCP to a ratio g(β) - ε is NP-hard and we give r(β)-approximation algorithms for the same problem where g(β) and r(β) are functions of β. If β < (3-3~(1/2))/2, we have r(β) = g(β) = 1, i.e., ∆_β-SpHCP is polynomial time solvable. If (3-3~(1/2))/2 <β≤2/3, we have r(β) = g(β) = (1+2β-2β~2)/(4(1-β)). For 2/3≤ β ≤ 1, r(β) = min{(1+2β-2β~2)/(4(1-β)), 1 + (4β~2)/(5β+1)}. Moreover, for β ≥ 1, we have r(β) = min{β +(4β~2-2β)/2+β, 2β+1}. For β ≥ 2, the approximability of the problem (i.e., upper and lower bound) is linear in β.
展开▼
