給定一個度量圖G=(V,E,w)、一個特定的點c∈V和一個整數p，令T為G的一個生成樹，並且T的深度為二、T以c為樹根、c連接的p個點稱為中繼站、剩下的每個點都連接到一個中繼站。星狀p-中繼站路由問題是要找出一個這樣的生成樹T，並且讓任意兩點在T中的距離總和最小。在先前的研究中，星狀p-中繼站路由問題被證明為NP-hard的問題，並且有一個4近似演算法被提出。在本篇論文中，我們用較簡單的問題轉換以及更容易閱讀的證明過程，證明了星狀p-中繼站路由問題為NP-hard的問題。此外，我們提出了一個能在O(n^2)時間內執行完成的3近似演算法，其中n為輸入圖的點的個數。相較於先前的研究結果，我們提出的近似演算法達到更良好的近似比值。

Given a metric graph G=(V,E,w), a specific vertex c∈V, and an integer p, let T be a depth-2 spanning tree of G rooted at c such that c is adjacent to p vertices called hubs and each of the remaining vertices is adjacent to a hub. The STAR p-HUB ROUTING COST PROBLEM is to find a spanning tree T of G and minimize the sum of distances between all pairs of vertices in T. In the previous research, the STAR p-HUB ROUTING COST PROBLEM was proved to be NP-hard and a 4-approximation algorithm was given. In this paper, we prove that the STAR p-HUB ROUTING COST PROBLEM is NP-hard by a simpler reduction and more readable process of proof. Moreover, we present a 3-approximation algorithm running in time O(n^2) for the same problem where n is the number of vertices in the input graph. The proposed algorithm improves the approximation ratio of the previous result.

[ 1 ] Sibel A Alumur, James F Campbell, Ivan Contreras, Bahar Y Kara, Vladimir Marianov, and Morton E O'Kelly. Perspectives on modeling hub location problems. European Journal of Operational Research, 2020.
[ 2 ] Li-Hsuan Chen, Dun-Wei Cheng, Sun-Yuan Hsieh, Ling-Ju Hung, Ralf Klasing, Chia-Wei Lee, and Bang Ye Wu. Approximability and inapproximability of the star p-hub center problem with parameterized triangle inequality. Journal of Computer and System Sciences, 92:92–112, 2018.
[ 3 ] Li-Hsuan Chen, Dun-Wei Cheng, Sun-Yuan Hsieh, Ling-Ju Hung, Chia-Wei Lee, and Bang Ye Wu. Approximation algorithms for single allocation k-hub center problem. In Proceedings of the 33rd Workshop on Combinatorial Mathematics and Computation Theory (CMCT 2016), pages 13–18, 2016.
[ 4 ] Li-Hsuan Chen, Dun-Wei Cheng, Sun-Yuan Hsieh, Ling-Ju Hung, Chia-Wei Lee, and Bang Ye Wu. Approximation algorithms for the star k-hub center problem in metric graphs. In International Computing and Combinatorics Conference, pages 222–234. Springer, 2016.
[ 5 ] Li-Hsuan Chen, Sun-Yuan Hsieh, Ling-Ju Hung, and Ralf Klasing. The approximability of the p-hub center problem with parameterized triangle inequality. In International Computing and Combinatorics Conference, pages 112–123. Springer, 2017.
[ 6 ] Li-Hsuan Chen, Sun-Yuan Hsieh, Ling-Ju Hung, and Ralf Klasing. Approximation algorithms for the p-hub center routing problem in parameterized metric graphs. Theoretical Computer Science, 806:271–280, 2020.
[ 7 ] Ivan Contreras. Hub location problems. In Location science, pages 311–344. Springer, 2015.
[ 8 ] Reza Zanjirani Farahani, Masoud Hekmatfar, Alireza Boloori Arabani, and Ehsan Nikbakhsh. Hub location problems: A review of models, classification, solution techniques, and applications. Computers & Industrial Engineering, 64(4):1096–1109, 2013.
[ 9 ] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W. H. Freeman, first edition edition, 1979.
[ 10 ] Sun-Yuan Hsieh, Li-Hsuan Chen, and Wei Lu. An approximation algorithm for star p-hub routing cost problem. In International Computer Symposium, pages 524–531. Springer, 2018.
[ 11 ] Sun-Yuan Hsieh and Shih-Shun Kao. A survey of hub location problems. Journal of Interconnection Networks, 19(01):1940005, 2019.
[ 12 ] Te C Hu. Optimum communication spanning trees. SIAM Journal on Computing, 3(3):188–195, 1974.
[ 13 ] Rafay Ishfaq and Charles R Sox. Design of intermodal logistics networks with hub delays. European Journal of Operational Research, 220(3):629–641, 2012.
[ 14 ] Masaru Iwasa, Hiroo Saito, and Tomomi Matsui. Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems. Discrete Applied Mathematics, 157(9):2078–2088, 2009.
[ 15 ] David S Johnson, Jan Karel Lenstra, and A. H. G. Rinnooy Kan. The complexity of the network design problem. Networks, 8(4):279–285, 1978.
[ 16 ] Hongyu Liang. The hardness and approximation of the star p-hub center problem. Operations Research Letters, 41(2):138–141, 2013.
[ 17 ] Chen-Wan Lin and Bang Ye Wu. On the minimum routing cost clustered tree problem. Journal of Combinatorial Optimization, 33(3):1106–1121, 2017.
[ 18 ] Cheng-Chang Lin, Jr-Yung Lin, and Yin-Chieh Chen. The capacitated p-hub median problem with integral constraints: An application to a chinese air cargo network. Applied Mathematical Modelling, 36(6):2777–2787, 2012.
[ 19 ] Morton E O'Kelly. A quadratic integer program for the location of interacting hub facilities. European journal of operational research, 32(3):393–404, 1987.
[ 20 ] Santiago Valdés Ravelo and Carlos Eduardo Ferreira. A PTAS for the metric case of the optimum weighted source–destination communication spanning tree problem. Theoretical Computer Science, 771:9–22, 2019.
[ 21 ] Hamid Tikani, Mahboobeh Honarvar, and Yahia Zare Mehrjerdi. Joint optimization of star p-hub median problem and seat inventory control decisions considering a hybrid routing transportation system. International Journal of Supply and Operations Management, 3(3):1442– 1465, 2016.
[ 22 ] Adriano D Vasconcelos, Carlos D Nassi, and Luiz AS Lopes. The uncapacitated hub location problem in networks under decentralized management. Computers & Operations Research, 38(12):1656–1666, 2011.
[ 23 ] Xing Wang, Guangting Chen, Yong Chen, Guohui Lin, Yonghao Wang, and An Zhang. Improved hardness and approximation results for single allocation hub location. In International Conference on Algorithmic Applications in Management, pages 85–96. Springer, 2020.
[ 24 ] Bang Ye Wu, Giuseppe Lancia, Vineet Bafna, Kun-Mao Chao, Ramamurthy Ravi, and Chuan Yi Tang. A polynomial-time approximation scheme for minimum routing cost spanning trees. SIAM Journal on Computing, 29(3):761–778, 2000.
[ 25 ] Hande Yaman. Star p-hub median problem with modular arc capacities. Computers & Operations Research, 35(9):3009–3019, 2008.
[ 26 ] Hande Yaman and Sourour Elloumi. Star p-hub center problem and star p-hub median problem with bounded path lengths. Computers & operations research, 39(11):2725–2732, 2012.