A complete weighted graph G = (V, E, ω) is called Δ_β-metric, for some β ≥ 1/2, if G satisfies the β-triangle inequality, i.e., ω(u, v) ≤ β · (ω(u, x) + ω(x, v)) for all vertices u, v, x ∈ V. Given a Δ_β-metric graph G = (V, E, ω) and an integer p, the Δ_β-pHUB CENTER PROBLEM (Δ_β-pHCP) is to find a spanning subgraph H~* of G such that (i) vertices (hubs) in C~*{is contained in}V form a clique of size p in H~*; (ii) vertices (non-hubs) in VC~* form an independent set in H~*; (iii) each non-hub v ∈ VC~* is adjacent to exactly one hub in C~*; and (iv) the diameter D(H~*) is minimized. For β = 1, Δ_β-pHCP is NP-hard. (Chen et al., CMCT 2016) proved that for any ε > 0, it is NP-hard to approximate the Δ_β-pHCP to within a ratio 4/3 - ε for β = 1. In the same paper, a 5/3-approximation algorithm was given for Δ_β-pHCP for β = 1, In this paper, we study Δ_β-pHCP for all β ≥ 1/2. We show that for any ε > 0, to approximate the Δ_β-pHCP 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., Δ_β-pHCP is polynomial time solvable. If 3-{the square root of}3/2 < β ≤ 2/3, we have r(β) = 9(β) = 3β-2β~2/3(1-β). For 2/3 ≤ β ≤ 5+{the square root of}5/10, r(β) = g(β) = β + β~2. Moreover, for β ≥ 1, we have g(β) = β · 4β-1/3β-1 and r(β) = 2β, the approx-imability of the problem (i. e., upper and lower bound) is linear in β.
展开▼
