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, Δ_β-SpHCP 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-{the square root of}3/2, we have r(β) = g(β) = 1, i.e., Δ_β-SpHCP is polynomial time solvable. If 3-{the square root of}3/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 β.
展开▼
