# The approximability of the p-hub center problem with parameterized triangle inequality

Li Hsuan Chen, Sun Yuan Hsieh, Ling Ju Hung, Ralf Klasing

8 引文 斯高帕斯（Scopus）

## 摘要

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 Δβ -pHub 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 V \C form an independent set in H ; (iii) each non-hub v ∈ V \C 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 ratio43 − ε for β = 1. In the same paper, a53 -approximation algorithm was given for Δβ-pHCP for β = 1. In this paper, we study Δβ -pHCP for all β ≥12. 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−√23, we have r(β) = g(β) = 1, i.e., Δβ -pHCP is polynomial time solvable. If3−√23 < β ≤23, we have r(β) = g(β) =3β−2β23(1−β). For23 ≤ β ≤5+√105, r(β) = g(β) = β + β2. Moreover, for β ≥ 1, we have g(β) = β ·4β−13β−1 and r(β) = 2β, the approximability of the problem (i.e., upper and lower bound) is linear in β.

原文 English Computing and Combinatorics - 23rd International Conference, COCOON 2017, Proceedings Yixin Cao, Jianer Chen Springer Verlag 112-123 12 9783319623887 https://doi.org/10.1007/978-3-319-62389-4_10 Published - 2017 23rd International Conference on Computing and Combinatorics, COCOON 2017 - Hong Kong, China持續時間: 2017 八月 3 → 2017 八月 5

### 出版系列

名字 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10392 LNCS 0302-9743 1611-3349

### Other

Other 23rd International Conference on Computing and Combinatorics, COCOON 2017 China Hong Kong 17-08-03 → 17-08-05

• 理論電腦科學
• 電腦科學(全部)