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

PY - 2017/1/1

Y1 - 2017/1/1

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 -