{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T04:57:36Z","timestamp":1769921856173,"version":"3.49.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2022,2,26]],"date-time":"2022-02-26T00:00:00Z","timestamp":1645833600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,2,26]],"date-time":"2022-02-26T00:00:00Z","timestamp":1645833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,7]]},"DOI":"10.1007\/s00453-022-00941-z","type":"journal-article","created":{"date-parts":[[2022,2,26]],"date-time":"2022-02-26T06:02:47Z","timestamp":1645855367000},"page":"1993-2027","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Approximability of the Single Allocation p-Hub Center Problem with Parameterized Triangle Inequality"],"prefix":"10.1007","volume":"84","author":[{"given":"Li-Hsuan","family":"Chen","sequence":"first","affiliation":[]},{"given":"Sun-Yuan","family":"Hsieh","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5659-5507","authenticated-orcid":false,"given":"Ling-Ju","family":"Hung","sequence":"additional","affiliation":[]},{"given":"Ralf","family":"Klasing","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,26]]},"reference":[{"key":"941_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2007.06.008","volume":"190","author":"SA Alumur","year":"2008","unstructured":"Alumur, S.A., Kara, B.Y.: Network hub location problems: the state of the art. Eur. J. Oper. Res. 190, 1\u201321 (2008)","journal-title":"Eur. J. Oper. Res."},{"key":"941_CR2","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.1024","volume":"38","author":"T Andreae","year":"2001","unstructured":"Andreae, T.: On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality. Networks 38, 59\u201367 (2001)","journal-title":"Networks"},{"key":"941_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0895480192240226","volume":"8","author":"T Andreae","year":"1995","unstructured":"Andreae, T., Bandelt, H.-J.: Performance guarantees for approximation algorithms depending on parameterized triangle inequalities. SIAM J. Discret. Math. 8, 1\u201316 (1995)","journal-title":"SIAM J. Discret. Math."},{"key":"941_CR4","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0020-0190(99)00160-X","volume":"73","author":"MA Bender","year":"2000","unstructured":"Bender, M.A., Chekuri, C.: Performance guarantees for the TSP with a parameterized triangle inequality. Inf. Process. Lett. 73, 17\u201321 (2000)","journal-title":"Inf. Process. Lett."},{"key":"941_CR5","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.-J., Bongartz, D., Hromkovi\u010d, J., Klasing, R., Proietti, G., Seibert, S., Unger, W.: On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality. In: Proceedings of the FSTTCS 2002, LNCS 2556, Springer 2002, pp.\u00a059\u201370. Full version in Theoretical Computer Science 326 (2004), 137\u2013153","DOI":"10.1007\/3-540-36206-1_7"},{"key":"941_CR6","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.-J., Bongartz, D., Hromkovi\u010d, J., Klasing, R., Proietti, G., Seibert, S., Unger, W.: On $$k$$-edge-connectivity problems with sharpened triangle inequality. In: R.\u00a0Petreschi, G.\u00a0Persiano, R.\u00a0Silvestri (eds.), Algorithms and Complexity, Proceedings of the 5th Italian Conference, CIAC 2003, LNCS 2653, Springer, pp.\u00a0189\u2013200 (2003)","DOI":"10.1007\/3-540-44849-7_24"},{"issue":"4","key":"941_CR7","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1016\/j.jda.2008.03.003","volume":"6","author":"H-J B\u00f6ckenhauer","year":"2008","unstructured":"B\u00f6ckenhauer, H.-J., Bongartz, D., Hromkovi\u010d, J., Klasing, R., Proietti, G., Seibert, S., Unger, W.: On $$k$$-connectivity problems with sharpened triangle inequality. J. Dis. Algorithms 6(4), 605\u2013617 (2008)","journal-title":"J. Dis. Algorithms"},{"key":"941_CR8","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S0020-0190(00)00089-2","volume":"75","author":"H-J B\u00f6ckenhauer","year":"2000","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Klasing, R., Seibert, S., Unger, W.: Approximation algorithms for the TSP with sharpened triangle inequality. Inf. Process. Lett. 75, 133\u2013138 (2000)","journal-title":"Inf. Process. Lett."},{"key":"941_CR9","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Klasing, R., Seibert, S., Unger, W.: Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem (Extended Abstract). In: Proceedings of the CIAC 2000, LNCS 1767, Springer 2000, pp.\u00a072\u201386. Full version in Theoretical Computer Science 285, pp.\u00a03\u201324 (2002)","DOI":"10.1016\/S0304-3975(01)00287-0"},{"key":"941_CR10","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Klasing, R., Seibert, S., W. Unger: An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inequality (Extended Abstract). In: Proceedings of STACS 2000, LNCS 1770, Springer, pp. 382-394 (2000)","DOI":"10.1007\/3-540-46541-3_32"},{"key":"941_CR11","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Seibert, S.: Stability of approximation. In T. F. Gonzalez (ed.): Handbook of Approximation Algorithms and Metaheuristics, Second Edition: Methodologies and Traditional Applications, Volume 1, CRC Press, Chapter 27 (2018)","DOI":"10.1201\/9781351236423-27"},{"key":"941_CR12","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1051\/ita:2000115","volume":"34","author":"H-J B\u00f6ckenhauer","year":"2000","unstructured":"B\u00f6ckenhauer, H.-J., Seibert, S.: Improved lower bounds on the approximability of the traveling salesman problem. RAIRO Theor. Inform. Appl. 34, 213\u2013255 (2000)","journal-title":"RAIRO Theor. Inform. Appl."},{"issue":"2","key":"941_CR13","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/s11590-016-1004-x","volume":"11","author":"J Brimberg","year":"2017","unstructured":"Brimberg, J., Mladenovi\u0107, N., Todosijevi\u0107, R., Uro\u0161evi\u0107, D.: General variable neighborhood search for the uncapacitated single allocation $$p$$-hub center problem. Optim. Lett. 11(2), 377\u2013388 (2017)","journal-title":"Optim. Lett."},{"key":"941_CR14","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1016\/0377-2217(94)90318-2","volume":"72","author":"JF Campbell","year":"1994","unstructured":"Campbell, J.F.: Integer programming formulations of discrete hub location problems. Eur. J. Oper. Res. 72, 387\u2013405 (1994)","journal-title":"Eur. J. Oper. Res."},{"key":"941_CR15","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/978-3-642-56082-8_12","volume-title":"Facility Location: Applications and Theory","author":"JF Campbell","year":"2002","unstructured":"Campbell, J.F., Ernst, A.T.: Hub location problems. In: Drezner, Z., Hamacher, H.W. (eds.) Facility Location: Applications and Theory, pp. 373\u2013407. Springer, Berlin (2002)"},{"key":"941_CR16","unstructured":"Chen, L.-H., Cheng, D.-W., Hsieh, S.-Y., Hung, L.-J., Lee, C.-W., Wu, B.Y.: Approximation algorithms for single allocation $$k$$-hub center problem. In: Proceedings of the 33rd Workshop on Combinatorial Mathematics and Computation Theory (CMCT\u00a02016), pp\u00a013\u201318 (2016)"},{"key":"941_CR17","doi-asserted-by":"crossref","unstructured":"Chen, L.-H., Hsieh, S.-Y., Hung, L.-J., Klasing, R., Lee, C.-W., Wu, B.Y.: On the complexity of the star $$p$$-hub center problem with parameterized triangle inequality. In: Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC 2017), LNCS\u00a010236, pp\u00a0152\u2013163, 2017. Full version in Journal of Computer System Sciences 92, pp.\u00a092\u2013112 (2018)","DOI":"10.1007\/978-3-319-57586-5_14"},{"key":"941_CR18","doi-asserted-by":"crossref","unstructured":"Chen, L.-H., Cheng, D.-W., Hsieh, S.-Y., Hung, L.-J., Lee, C.-W., Wu, B.Y.: Approximation algorithms for the star $$k$$-hub center problem in metric graphs. In: Proceedings of the 22nd International Computing and Combinatorics Conference\u00a0(COCOON\u00a02016), LNCS 9797, pp.\u00a0222\u2013234 (2016)","DOI":"10.1007\/978-3-319-42634-1_18"},{"key":"941_CR19","doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. Proc. STOC 2014, 624\u2013633 (2014)","DOI":"10.1145\/2591796.2591884"},{"key":"941_CR20","doi-asserted-by":"publisher","first-page":"2230","DOI":"10.1016\/j.cor.2008.08.021","volume":"36","author":"AT Ernst","year":"2009","unstructured":"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\u20132241 (2009)","journal-title":"Comput. Oper. Res."},{"key":"941_CR21","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, San Francisco (1979)"},{"key":"941_CR22","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/978-3-642-60207-8_21","volume-title":"Jewels are Forever","author":"J Hromkovi\u010d","year":"1999","unstructured":"Hromkovi\u010d, J.: Stability of approximation algorithms and the knapsack problem. In: Karhum\u00e4ki, J., Maurer, H., Paun, G., Rozenberg, G. (eds.) Jewels are Forever, pp. 238\u2013249. Springer, New York (1999)"},{"key":"941_CR23","volume-title":"Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics","author":"J Hromkovi\u010d","year":"2003","unstructured":"Hromkovi\u010d, J.: Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, 2nd edn. Springer, New York (2003)","edition":"2"},{"key":"941_CR24","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1016\/S0377-2217(99)00274-X","volume":"125","author":"BY Kara","year":"2000","unstructured":"Kara, B.Y., Tansel, B.\u00c7.: On the single-assignment $$p$$-hub center problem. Eur. J. Oper. Res. 125, 648\u2013655 (2000)","journal-title":"Eur. J. Oper. Res."},{"key":"941_CR25","doi-asserted-by":"crossref","unstructured":"Klasing, R., M\u00f6mke, T.: A modern view on stability of approximation. In: Adventures Between Lower Bounds and Higher Altitudes: Essays Dedicated to Juraj Hromkovi\u010d on the Occasion of His 60th Birthday, LNCS 11011, pp 393\u2013408 (2018)","DOI":"10.1007\/978-3-319-98355-4_22"},{"key":"941_CR26","doi-asserted-by":"crossref","unstructured":"Liang, H.: The hardness and approximation of the star $$p$$-hub center problem. Oper. Res. Lett. 41, 138\u2013141 (2013)","DOI":"10.1016\/j.orl.2012.12.007"},{"key":"941_CR27","doi-asserted-by":"publisher","first-page":"3143","DOI":"10.1016\/j.cor.2008.07.011","volume":"36","author":"T Meyer","year":"2009","unstructured":"Meyer, T., Ernst, A., Krishnamoorthy, M.: A 2-phase algorithm for solving the single allocation $$p$$-hub center problem. Comput. Oper. Res. 36, 3143\u20133151 (2009)","journal-title":"Comput. Oper. Res."},{"key":"941_CR28","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1016\/j.ipl.2015.06.003","volume":"115","author":"T M\u00f6mke","year":"2015","unstructured":"M\u00f6mke, T.: An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality. Inf. Process. Lett. 115, 866\u2013871 (2015)","journal-title":"Inf. Process. Lett."},{"key":"941_CR29","first-page":"399","volume":"33","author":"FS Pamuk","year":"2001","unstructured":"Pamuk, F.S., Sepil, C.: A solution to the hub center problem via a single-relocation algorithm with tabu search. IIE Trans. 33, 399\u2013411 (2001)","journal-title":"IIE Trans."},{"key":"941_CR30","first-page":"405","volume":"6","author":"M Rabbani","year":"2015","unstructured":"Rabbani, M., Kazemi, S.M.: Solving uncapacitated multiple allocation $$p$$-hub center problem by Dijkstras algorithm-based genetic algorithm and simulated annealing. Int. J. Ind. Eng. Comput. 6, 405\u2013418 (2015)","journal-title":"Int. J. Ind. Eng. Comput."},{"issue":"6","key":"941_CR31","doi-asserted-by":"publisher","first-page":"1109","DOI":"10.1007\/s11590-015-0867-6","volume":"11","author":"R Todosijevi\u0107","year":"2017","unstructured":"Todosijevi\u0107, R., Uro\u0161evi\u0107, D., Mladenovi\u0107, N., Hanafi, S.: A general variable neighborhood search for solving the uncapacitated $$r$$-allocation $$p$$-hub median problem. Optim. Lett. 11(6), 1109\u20131121 (2017)","journal-title":"Optim. Lett."},{"key":"941_CR32","doi-asserted-by":"publisher","first-page":"2725","DOI":"10.1016\/j.cor.2012.02.005","volume":"39","author":"H Yaman","year":"2012","unstructured":"Yaman, H., Elloumi, S.: Star $$p$$-hub center problem and star $$p$$-hub median problem with bounded path lengths. Comput. Oper. Res. 39, 2725\u20132732 (2012)","journal-title":"Comput. Oper. Res."},{"key":"941_CR33","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.cie.2012.09.006","volume":"64","author":"K Yang","year":"2013","unstructured":"Yang, K., Liu, Y., Yang, G.: An improved hybrid particle swarm optimization algorithm for fuzzy $$p$$-hub center problem. Comput. Ind. Eng. 64, 133\u2013142 (2013)","journal-title":"Comput. Ind. Eng."},{"key":"941_CR34","doi-asserted-by":"publisher","first-page":"2624","DOI":"10.1016\/j.asoc.2012.11.024","volume":"13","author":"K Yang","year":"2013","unstructured":"Yang, K., Liu, Y., Yang, G.: Solving fuzzy $$p$$-hub center problem by genetic algorithm incorporating local search. Appl. Soft Comput. 13, 2624\u20132632 (2013)","journal-title":"Appl. Soft Comput."},{"key":"941_CR35","doi-asserted-by":"publisher","first-page":"3987","DOI":"10.1016\/j.apm.2014.01.009","volume":"38","author":"K Yang","year":"2014","unstructured":"Yang, K., Liu, Y., Yang, G.: Optimizing fuzzy $$p$$-hub center problem with generalized value-at-risk criterion. Appl. Math. Model. 38, 3987\u20134005 (2014)","journal-title":"Appl. Math. Model."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00941-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00941-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00941-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T09:33:48Z","timestamp":1726738428000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00941-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,26]]},"references-count":35,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["941"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00941-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,26]]},"assertion":[{"value":"27 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}