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 -