TY - GEN

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

AU - Chen, Li Hsuan

AU - Hsieh, Sun Yuan

AU - Hung, Ling Ju

AU - Klasing, Ralf

AU - Lee, Chia Wei

AU - Wu, Bang Ye

N1 - Funding Information:
R. Klasing–Part of this work was done while Ralf Klasing was visiting the Department of Computer Science and Information Engineering at National Cheng Kung University. This study has been carried out in the frame of the “Investments for the future” Programme IdEx Bordeaux - CPU (ANR-10-IDEX-03-02). Research supported by the LaBRI under the “Projets émergents” program.
Funding Information:
Parts of this research were supported by the Ministry of Science and Technology of Taiwan under grants MOST 105–2221–E–006–164–MY3, MOST 103–2218–E–006–019–MY3, and MOST 103-2221-E-006-135-MY3. L.-H. Chen, L.-J. Hung (corresponding author), and C.-W. Lee are supported by the Ministry of Science and Technology of Taiwan under grants MOST 105–2811–E–006–071, –046, and –022, respectively.
Publisher Copyright:
© Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - 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 ƒÀ.

AB - 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 ƒÀ.

UR - http://www.scopus.com/inward/record.url?scp=85018428709&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85018428709&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-57586-5_14

DO - 10.1007/978-3-319-57586-5_14

M3 - Conference contribution

AN - SCOPUS:85018428709

SN - 9783319575858

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 152

EP - 163

BT - Algorithms and Complexity - 10th International Conference, CIAC 2017, Proceedings

A2 - Fotakis, Dimitris

A2 - Pagourtzis, Aris

A2 - Paschos, Vangelis Th.

PB - Springer Verlag

T2 - 10th International Conference on Algorithms and Complexity, CIAC 2017

Y2 - 24 May 2017 through 26 May 2017

ER -