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 -