Abstract
Given a metric graph \(G=(V, E, w)\) and a center \(c\in 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 \(\epsilon >0\), it is NP-hard to approximate the Star k-Hub Center Problem to within a ratio \(1.25-\epsilon \). 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 \(\epsilon > 0\), to approximate the Star k-Hub Center Problem to a ratio \(1.5 - \epsilon \) is NP-hard. Moreover, we give 2-approximation and \(\frac{5}{3}\)-approximation algorithms for the same problem.
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.
Ling-Ju Hung is supported by the Ministry of Science and Technology of Taiwan under grant MOST 104–2811–E–006–056.
Chia-Wei Lee is supported by the Ministry of Science and Technology of Taiwan under grant MOST 104-2811-E-006-037.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alumur, S.A., Kara, B.Y.: Network hub location problems: the state of the art. Netw. Hub Location Probl.: State Art 190, 1–21 (2008)
Campbell, J.F.: Integer programming formulations of discrete hub location problems. Eur. J. Oper. Res. 72, 387–405 (1994)
Campbell, J.F., Ernst, A.T.: Hub location problems. In: Drezner, Z., Hamacher, H.W. (eds.) Facility Location: Applications and Theory, pp. 373–407. Springer, Berlin (2002)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. The MIT Press, Cambridge (2009)
Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of STOC 2014, pp. 624–633 (2014)
Ernst, A.T., Hamacher, H., Jiang, H., Krishnamoorthy, M., Woeginger, G.: Uncapacitated single and multiple allocation \(p\)-hub center problem. Comput. Oper. Res. 36, 2230–2241 (2009)
Kara, B.Y., Tansel, B.Ç.: On the single-assignment \(p\)-hub center problem. Eur. J. Oper. Res. 125, 648–655 (2000)
Liang, H.: The hardness and approximation of the star \(p\)-hub center problem. Oper. Res. Lett. 41, 138–141 (2013)
Meyer, T., Ernst, A., Krishnamoorthy, M.: A 2-phase algorithm for solving the single allocation \(p\)-hub center problem. Comput. Oper. Res. 36, 3143–3151 (2009)
O’Kelly, M.E., Miller, H.J.: Solution strategies for the single facility minimax hub location problem. Pap. Reg. Sci. 70, 376–380 (1991)
Yaman, H., Elloumi, S.: Star \(p\)-hub center problem and star \(p\)-hub median problem with bounded path length. Comput. Oper. Res, 39, 2725–2732 (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Chen, LH., Cheng, DW., Hsieh, SY., Hung, LJ., Lee, CW., Wu, B.Y. (2016). Approximation Algorithms for the Star k-Hub Center Problem in Metric Graphs. In: Dinh, T., Thai, M. (eds) Computing and Combinatorics . COCOON 2016. Lecture Notes in Computer Science(), vol 9797. Springer, Cham. https://doi.org/10.1007/978-3-319-42634-1_18
Download citation
DOI: https://doi.org/10.1007/978-3-319-42634-1_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-42633-4
Online ISBN: 978-3-319-42634-1
eBook Packages: Computer ScienceComputer Science (R0)