# On the complexity of the star p-hub center problem with parameterized triangle inequality

Li Hsuan Chen, Sun Yuan Hsieh, Ling Ju Hung, Ralf Klasing, Chia Wei Lee, Bang Ye Wu

7 引文 斯高帕斯（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). ƒÀ E (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. ã 3 2, we have r(ƒÀ) = g(ƒÀ) = 1, i.e., ƒ¢ƒÀ-SpHCP is polynomial time solvable. If 3. ã 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 ƒÀ.

原文 English Algorithms and Complexity - 10th International Conference, CIAC 2017, Proceedings Dimitris Fotakis, Aris Pagourtzis, Vangelis Th. Paschos Springer Verlag 152-163 12 9783319575858 https://doi.org/10.1007/978-3-319-57586-5_14 Published - 2017 10th International Conference on Algorithms and Complexity, CIAC 2017 - Athens, Greece持續時間: 2017 5月 24 → 2017 5月 26

### 出版系列

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

### Other

Other 10th International Conference on Algorithms and Complexity, CIAC 2017 Greece Athens 17-05-24 → 17-05-26

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