本研究以理論計算科學角度探討中繼站定位問題之近似穩定性質，從問題實例中探索關鍵特徵獲取問題複雜度分析。參數化三角不等式在特殊參數區間中的問題開發具備穩定性質的近似演算方法，並達成與區間參數高度相關成長的近似比率。將問題實例以參數化三角不等式區分，傳輸成本函式映射至問題複雜度的對應光譜。解析在不同參數區間下的三角不等式與中繼站定位問題之不可近似性關聯，開發與取決於區間參數的高效近似演算方法。

以關鍵特徵分析驅動本研究深入探討中心面向星狀中繼站定位問題，運用參數化三角不等式驗證中心面向星狀中繼站定問位問題在不同參數區間下對應的問題複雜度。將問題以多項式時間技巧轉換為著名的集合覆蓋問題，提出相對應的問題不可近似性假說；並針對分析參數區間提出能在多項式時間下求得的近似演算方法。部分參數區間中，中心面向星狀中繼站問題能以多項式時間技巧求得精確解；此外，所提出的近似演算方法在特殊區間參數條件下能達成可近似之最佳目標。

This dissertation studies the Hub Location problems through a theoretical perspective: stability of approximation. Searching for significant features from problem instances that capture the complexity. The approximation algorithms are stable concerning the significant features, β-metric graphs within a specific interval. The achieved approximation ratio is growing corresponding to the interval parameter β. Partition the transportation cost into an infinite spectrum according to the parameterized triangle inequality. This dissertation investigates the relationship between the inapproximability and the membership of distinct parameterized intervals under β-metric graphs. Conducting efficient approximation ratios depends on this spectrum parameter.

Investigating the significant features of the Star q-Hub Center Problem motivates this dissertation. This dissertation aims to verify the complexity of the Star q-Hub Center Problem by parameterized triangle inequality. Making inapproximability statements and demonstrating the complexity by reducing to the renowned NP-hard problem Set Cover. Another contribution of this dissertation is presenting polynomial-time strategies for solving the Star q-Hub Center Problem. For the parameterized interval from 1/2 to (3−√3)/2, the Star q-Hub Center Problem under β-metric graphs can be solved exactly by the proposed polynomial-time strategy. Besides, this dissertation also closes the gap in the inapproximability for the parameterized interval form (3−√3)/2 to 2/3.

[1] Alumur, S., and Kara, B. Y. A hub covering network design problem for cargo applications in turkey. Journal of the Operational Research Society 60, 10 (2009), 1349–1359.
[2] Andreae, T. On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality. Networks: An International Journal 38, 2 (2001), 59–67.
[3] Andreae, T., and Bandelt, H.-J. Performance guarantees for approximation algorithms depending on parametrized triangle inequalities. SIAM Journal on Discrete Mathematics 8, 1 (1995), 1–16.
[4] Ansari, A. H., and Moslehian, M. S. More on reverse triangle inequality in inner product spaces. International Journal of Mathematics and Mathematical Sciences 2005, 18 (2005), 2883–2893.
[5] Bahar, A., Ozgen, C., Leblebicio ¨ glu, K., and Halıcı, U. ˇ Artificial neural network estimator design for the inferential model predictive control of an industrial distillation column. Industrial & engineering chemistry research 43, 19 (2004), 6102–6111.
[6] Barnes, J. A., and Harary, F. Graph theory in network analysis. Social networks 5, 2 (1983), 235–244.
[7] Barthelemy, M. ´ Spatial networks. Physics Reports 499, 1-3 (2011), 1–101. 85
[8] Bashiri, M., Mirzaei, M., and Randall, M. Modeling fuzzy capacitated p-hub center problem and a genetic algorithm solution. Applied Mathematical Modelling 37, 5 (2013), 3513–3525.
[9] Bender, M. A., and Chekuri, C. Performance guarantees for the tsp with a parameterized triangle inequality. In Workshop on Algorithms and Data Structures (1999), Springer, pp. 80–85.
[10] Bender, M. A., and Chekuri, C. Performance guarantees for the tsp with a parameterized triangle inequality. Information Processing Letters 73, 1-2 (2000), 17–21.
[11] Bjerregaard, T., and Mahadevan, S. A survey of research and practices of network-on-chip. ACM Computing Surveys (CSUR) 38, 1 (2006), 1–es.
[12] Bockenhauer, H.-J., Bongartz, D., Hromkovi ¨ c, J., Klasing, R., Proi- ˇetti, G., Seibert, S., and Unger, W. On k-edge-connectivity problems with sharpened triangle inequality. In Italian Conference on Algorithms and Complexity (2003), Springer, pp. 189–200.
[13] Bockenhauer, H.-J., Bongartz, D., Hromkovi ¨ c, J., Klasing, R., Proi- ˇetti, G., Seibert, S., and Unger, W. On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality. Theoretical computer science 326, 1-3 (2004), 137–153.
[14] Bockenhauer, H.-J., Bongartz, D., Hromkovi ¨ c, J., Klasing, R., Proi- ˇetti, G., Seibert, S., and Unger, W. On k-connectivity problems with sharpened triangle inequality. Journal of Discrete Algorithms 6, 4 (2008), 605–617. 86
[15] Bockenhauer, H.-J., Freiermuth, K., Hromkovi ¨ c, J., M ˇ omke, T., ¨Sprock, A., and Steffen, B. Steiner tree reoptimization in graphs with sharpened triangle inequality. Journal of discrete algorithms 11 (2012), 73–86.
[16] Bockenhauer, H.-J., Hromkovi ¨ c, J., Klasing, R., Seibert, S., and Unger, ˇW. Approximation algorithms for the tsp with sharpened triangle inequality. Information Processing Letters 75, 3 (2000), 133–138.
[17] Bockenhauer, H.-J., Hromkovi ¨ c, J., Klasing, R., Seibert, S., and Unger, ˇW. Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. Theoretical Computer Science 285, 1 (2002), 3–24.
[18] Bockenhauer, H.-J., Hromkovi ¨ c, J., and Seibert, S. ˇ Stability of approximation. In Handbook of approximation algorithms and metaheuristics, vol. 10. Chapman & Hall/CRC, 2007, pp. 31–1.
[19] Bockenhauer, H.-J., and Seibert, S. ¨ Improved lower bounds on the approximability of the traveling salesman problem. RAIRO-Theoretical Informatics and Applications 34, 3 (2000), 213–255.
[20] Bryan, D. L., and O’kelly, M. E. Hub-and-spoke networks in air transportation: an analytical review. Journal of regional science 39, 2 (1999), 275–295.
[21] Burt, R. S. The social structure of competition. Networks in the knowledge economy 13 (2003), 57–91.
[22] Calık, H., Alumur, S. A., Kara, B. Y., and Karasan, O. E. A tabusearch based heuristic for the hub covering problem over incomplete hub networks. Computers & Operations Research 36, 12 (2009), 3088–3096. 87
[23] Campbell, J. F. Integer programming formulations of discrete hub location problems. European Journal of Operational Research 72, 2 (1994), 387–405.
[24] Campbell, J. F. Hub location and the p-hub median problem. Operations research 44, 6 (1996), 923–935.
[25] Campbell, J. F., and O’Kelly, M. E. Twenty-five years of hub location research. Transportation Science 46, 2 (2012), 153–169.
[26] Canovas, L., Garc ´ ´ıa, S., and Mar´ın, A. Solving the uncapacitated multiple allocation hub location problem by means of a dual-ascent technique. European Journal of Operational Research 179, 3 (2007), 990–1007.
[27] Carnoy, M., and Castells, M. Globalization, the knowledge society, and the network state: Poulantzas at the millennium. Global networks 1, 1 (2001), 1–18.
[28] Casciaro, T. Seeing things clearly: Social structure, personality, and accuracy in social network perception. Social Networks 20, 4 (1998), 331–351.
[29] Chen, J.-F. A hybrid heuristic for the uncapacitated single allocation hub location problem. Omega 35, 2 (2007), 211–220.
[30] Chen, L.-H., Hsieh, S.-Y., Hung, L.-J., Klasing, R., Lee, C.-W., and Wu, B. Y. On the complexity of the star p-hub center problem with parameterized triangle inequality. In International Conference on Algorithms and Complexity (2017), Springer, pp. 152–163.
[31] Chen, W., Pi, L., and Shi, L. Nested partitions and its applications to the intermodal hub location problem. In Optimization and logistics challenges in the enterprise. Springer, 2009, pp. 229–251.
88
[32] Contreras, I. Hub location problems. In Location science. Springer, 2015, pp. 311–344.
[33] Cook, K. S., and Whitmeyer, J. M. Two approaches to social structure: Exchange theory and network analysis. Annual review of Sociology 18, 1 (1992), 109–127.
[34] Correia, I., Nickel, S., and Saldanha-da Gama, F. The capacitated singleallocation hub location problem revisited: A note on a classical formulation. European Journal of Operational Research 207, 1 (2010), 92–96.
[35] Crainic, T. G., and Kim, K. H. Intermodal transportation. Handbooks in operations research and management science 14 (2007), 467–537.
[36] da Grac¸a Costa, M., Captivo, M. E., and Cl´ımaco, J. Capacitated single allocation hub location problem—a bi-criteria approach. Computers & operations research 35, 11 (2008), 3671–3695.
[37] de Camargo, R. S., and Miranda, G. Single allocation hub location problem under congestion: Network owner and user perspectives. Expert Systems with Applications 39, 3 (2012), 3385–3391.
[38] de Camargo, R. S., Miranda Jr, G., and Luna, H. P. Benders decomposition for the uncapacitated multiple allocation hub location problem. Computers & operations research 35, 4 (2008), 1047–1064.
[39] de Sa, E. M., Morabito, R., and de Camargo, R. S. ´ Benders decomposition applied to a robust multiple allocation incomplete hub location problem. Computers & Operations Research 89 (2018), 31–50. 89
[40] Dinur, I., and Steurer, D. Analytical approach to parallel repetition. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing (2014), pp. 624–633.
[41] Ebery, J., Krishnamoorthy, M., Ernst, A., and Boland, N. The capacitated multiple allocation hub location problem: Formulations and algorithms. European journal of operational research 120, 3 (2000), 614–631.
[42] Eiselt, H. A., and Marianov, V. Foundations of location analysis, vol. 155. Springer Science & Business Media, 2011.
[43] Ernst, A. T., and Krishnamoorthy, M. Efficient algorithms for the uncapacitated single allocation p-hub median problem. Location science 4, 3 (1996), 139–154.
[44] Ernst, A. T., and Krishnamoorthy, M. An exact solution approach based on shortest-paths for p-hub median problems. INFORMS Journal on Computing 10, 2 (1998), 149–162.
[45] Ernst, A. T., and Krishnamoorthy, M. Solution algorithms for the capacitated single allocation hub location problem. Annals of operations Research 86 (1999), 141–159.
[46] Fagin, R., and Stockmeyer, L. Relaxing the triangle inequality in pattern matching. International Journal of Computer Vision 30, 3 (1998), 219–231.
[47] Farahani, R. Z., Hekmatfar, M., Arabani, A. B., and Nikbakhsh, E.
Hub location problems: A review of models, classification, solution techniques, and applications. Computers & Industrial Engineering 64, 4 (2013), 1096–1109.
[48] Flory, P. J. Statistical mechanics of swelling of network structures. The Journal of Chemical Physics 18, 1 (1950), 108–111. 90
[49] Frank, H. Optimum locations on a graph with probabilistic demands. Operations Research 14, 3 (1966), 409–421.
[50] Gao, Y., and Qin, Z. A chance constrained programming approach for uncertain p-hub center location problem. Computers & Industrial Engineering 102 (2016), 10–20.
[51] Garey, M. R., and Johnson, D. S. Computers and intractability, vol. 174. freeman San Francisco, 1979.
[52] Guimaraes, V. T., Freitas, C. M. D. S., Sadre, R., Tarouco, L. M. R.,
and Granville, L. Z. A survey on information visualization for network and service management. IEEE Communications Surveys & Tutorials 18, 1 (2015), 285–323.
[53] Hakimi, S. L. Optimum locations of switching centers and the absolute centers and medians of a graph. Operations research 12, 3 (1964), 450–459.
[54] Hekmatfar, M., and Pishvaee, M. Hub location problem. In Facility Location. Springer, 2009, pp. 243–270.
[55] Hromkovic, J. ˇ Stability of approximation algorithms and the knapsack problem. In Jewels are forever. Springer, 1999, pp. 238–249.
[56] Hromkovic, J. ˇ Algorithmics for hard problems: introduction to combinatorial optimization, randomization, approximation, and heuristics. Springer Science & Business Media, 2013.
[57] Kali, R., and Reyes, J. The architecture of globalization: a network approach to international economic integration. Journal of International Business Studies 38, 4 (2007), 595–620. 91
[58] Kara, B. Y., and Tansel, B. C. On the single-assignment p-hub center problem. European Journal of Operational Research 125, 3 (2000), 648–655.
[59] Kara, B. Y., and Tansel, B. C. The single-assignment hub covering problem: Models and linearizations. Journal of the Operational Research Society 54, 1 (2003), 59–64.
[60] Khamiyev, I., Gabidolla, M., Iskakov, A., and Demirci, M. F. Reducing triangle inequality violations with deep learning and its application to image retrieval. In International Symposium on Visual Computing (2020), Springer, pp. 310–318.
[61] Kleinberg, J. M. Challenges in mining social network data: processes, privacy, and paradoxes. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining (2007), pp. 4–5.
[62] Klincewicz, J. G. Hub location in backbone/tributary network design: a review. Location Science 6, 1-4 (1998), 307–335.
[63] Klose, A., and Drexl, A. Facility location models for distribution system design. European journal of operational research 162, 1 (2005), 4–29.
[64] Kuby, M. J., and Gray, R. G. The hub network design problem with stopovers and feeders: The case of federal express. Transportation Research Part A: Policy and Practice 27, 1 (1993), 1–12.
[65] Kumar, S., Jantsch, A., Soininen, J.-P., Forsell, M., Millberg, M.,
Oberg, J., Tiensyrja, K., and Hemani, A. A network on chip architecture
and design methodology. In Proceedings IEEE Computer Society Annual Symposium on VLSI. New Paradigms for VLSI Systems Design. ISVLSI 2002 (2002), IEEE, pp. 117–124. 92
[66] Lee, Y., Lim, B. H., and Park, J. S. A hub location problem in designing digital data service networks: Lagrangian relaxation approach. Location Science 4, 3 (1996), 185–194.
[67] Liang, H. The hardness and approximation of the star p-hub center problem. Operations Research Letters 41, 2 (2013), 138–141.
[68] Maligranda, L. Some remarks on the triangle inequality for norms. Banach Journal of Mathematical Analysis 2, 2 (2008), 31–41.
[69] Mayer, G., and Wagner, B. Hublocator: an exact solution method for the multiple allocation hub location problem. Computers & Operations Research 29, 6 (2002), 715–739.
[70] Milanov, D., Milanova, Y. V., and Kholshevnikov, K. Relaxed triangle inequality for the orbital similarity criterion by southworth and hawkins and its variants. Celestial Mechanics and Dynamical Astronomy 131, 1 (2019), 5.
[71] Mohammadi, M., Jula, P., and Tavakkoli-Moghaddam, R. Reliable singleallocation hub location problem with disruptions. Transportation Research Part E: Logistics and Transportation Review 123 (2019), 90–120.
[72] Momke, T. ¨ An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality. Information Processing Letters 115, 11 (2015), 866–871.
[73] Moore, A. The anchors hierachy: Using the triangle inequality to survive high dimensional data. arXiv preprint arXiv:1301.3877 (2013).
[74] Neelakanta, P. S., and De Groff, D. F. Neural network modeling: Statistical mechanics and cybernetic perspectives. CRC Press, 2018.
93
[75] O’kelly, M. E. The location of interacting hub facilities. Transportation science 20, 2 (1986), 92–106.
[76] O’kelly, M. E. A quadratic integer program for the location of interacting hub facilities. European journal of operational research 32, 3 (1987), 393–404.
[77] O’Kelly, M. E. A geographer’s analysis of hub-and-spoke networks. Journal of transport Geography 6, 3 (1998), 171–186.
[78] O’Kelly, M. E., and Miller, H. J. The hub network design problem: a review and synthesis. Journal of Transport Geography 2, 1 (1994), 31–40.
[79] O’Kelly, M. E. Fuel burn and environmental implications of airline hub networks. Transportation Research Part D: Transport and Environment 17, 7 (2012), 555–567.
[80] Puerto, J., Ramos, A., and Rodr´ıguez-Ch´ıa, A. M. Single-allocation ordered median hub location problems. Computers & Operations Research 38, 2 (2011), 559–570.
[81] Puerto, J., Ramos, A., Rodr´ıguez-Ch´ıa, A. M., and Sanchez-Gil, M. C. ´Ordered median hub location problems with capacity constraints. Transportation Research Part C: Emerging Technologies 70 (2016), 142–156.
[82] ReVelle, C. S., and Eiselt, H. A. Location analysis: A synthesis and survey. European journal of operational research 165, 1 (2005), 1–19.
[83] Sim, T., Lowe, T. J., and Thomas, B. W. The stochastic p-hub center problem with service-level constraints. Computers & operations research 36, 12 (2009), 3166–3177. 94
[84] Skorin-Kapov, D., Skorin-Kapov, J., and O’Kelly, M. Tight linear programming relaxations of uncapacitated p-hub median problems. European journal of operational research 94, 3 (1996), 582–593.
[85] Toh, R. S., and Higgins, R. G. The impact of hub and spoke network centralization and route monopoly on domestic airline profitability. Transportation journal (1985), 16–27.
[86] Weiss, G. M. Data mining in telecommunications. In Data Mining and Knowledge Discovery Handbook. Springer, 2005, pp. 1189–1201.
[87] Wheeler, W. C. The triangle inequality and character analysis.
[88] Wu, S. A sharpened version of the fundamental triangle inequality. Mathematical Inequalities and Applications 11, 3 (2008), 477.
[89] Yaman, H., and Elloumi, S. Star p-hub center problem and star p-hub median problem with bounded path lengths. Computers & operations research 39, 11 (2012), 2725–2732.
[90] Zhang, T., Li, W., and Li, J. An improved approximation algorithm for the atsp with parameterized triangle inequality. Journal of Algorithms 64, 2-3 (2009), 74–78.