TY - GEN
T1 - Approximation algorithms for the star k-hub center problem in metric graphs
AU - Chen, Li Hsuan
AU - Cheng, Dun Wei
AU - Hsieh, Sun Yuan
AU - Hung, Ling Ju
AU - Lee, Chia Wei
AU - Wu, Bang Ye
N1 - Funding Information:
Chia-Wei Lee is supported by the Ministry of Science and Technology of Taiwan under grant MOST 104-2811-E-006-037.
Funding Information:
This research is partially supported by the Ministry of Science and Technology of Taiwan under grants MOST 103–2218–E–006–019–MY3, MOST 103–2221–E–006–135–MY3, MOST 103–2221–E–006–134–MY2.
Funding Information:
Ling-Ju Hung is supported by the Ministry of Science and Technology of Taiwan under grant MOST 104–2811–E–006–056.
Publisher Copyright:
© Springer International Publishing Switzerland 2016.
PY - 2016
Y1 - 2016
N2 - Given a metric graph G = (V, E, w) and a center c ∈ V, and an integer k, the Star k-Hub Center Problem is to find a depth-2 spanning tree T of G rooted by c such that c has exactly k children and the diameter of T is minimized. Those children of c in T are called hubs. The Star k-Hub Center Problem is NP-hard. (Liang, Operations Research Letters, 2013) proved that for any ε > 0, it is NP-hard to approximate the Star k-Hub Center Problem to within a ratio 1.25 −ε. In the same paper, a 3.5-approximation algorithm was given for the Star k-Hub Center Problem. In this paper, we show that for any ε > 0, to approximate the Star k-Hub Center Problem to a ratio 1.5 − ε is NP-hard. Moreover, we give 2-approximation and 5/3-approximation algorithms for the same problem.
AB - Given a metric graph G = (V, E, w) and a center c ∈ V, and an integer k, the Star k-Hub Center Problem is to find a depth-2 spanning tree T of G rooted by c such that c has exactly k children and the diameter of T is minimized. Those children of c in T are called hubs. The Star k-Hub Center Problem is NP-hard. (Liang, Operations Research Letters, 2013) proved that for any ε > 0, it is NP-hard to approximate the Star k-Hub Center Problem to within a ratio 1.25 −ε. In the same paper, a 3.5-approximation algorithm was given for the Star k-Hub Center Problem. In this paper, we show that for any ε > 0, to approximate the Star k-Hub Center Problem to a ratio 1.5 − ε is NP-hard. Moreover, we give 2-approximation and 5/3-approximation algorithms for the same problem.
UR - http://www.scopus.com/inward/record.url?scp=84979266846&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84979266846&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-42634-1_18
DO - 10.1007/978-3-319-42634-1_18
M3 - Conference contribution
AN - SCOPUS:84979266846
SN - 9783319426334
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 222
EP - 234
BT - Computing and Combinatorics - 22nd International Conference, COCOON 2016, Proceedings
A2 - Dinh, Thang N.
A2 - Thai, My T.
PB - Springer Verlag
T2 - 22nd International Conference on Computing and Combinatorics, COCOON 2016
Y2 - 2 August 2016 through 4 August 2016
ER -