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 an integer p, the ∆_β-pH+_(UB) Center Problem (∆_β-pHCP) is to find a spanning subgraph H~* of G such that (i) vertices (hubs) in C~*⊂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 ∆_β-pRCP 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)/2, we have r(β) = g(β) = 1, i.e., ∆_β-pHCP is polynomial time solvable. If (3-√3)/2 < β ≤ 2/3, we have r(β) = g(β) = (3β-2β~2)/(3(1-β)). For 2/3 ≤ β ≤ (5+√5)/(10), r(β) = g(β) = β + β~2. Moreover, for β ≥ 1, we have g(β) = β ·(4β-1)/(3β-1) and r(β) = 2β, the approximability of the problem (i.e., upper and lower bound) is linear in β.
展开▼
