{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:24Z","timestamp":1759638084776,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319575858"},{"type":"electronic","value":"9783319575865"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-57586-5_14","type":"book-chapter","created":{"date-parts":[[2017,4,13]],"date-time":"2017-04-13T15:23:34Z","timestamp":1492097014000},"page":"152-163","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality"],"prefix":"10.1007","author":[{"given":"Li-Hsuan","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sun-Yuan","family":"Hsieh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ling-Ju","family":"Hung","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ralf","family":"Klasing","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chia-Wei","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bang Ye","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,4,14]]},"reference":[{"key":"14_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":"14_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":"14_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":"14_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties","author":"G Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, Heidelberg (1999)"},{"key":"14_CR5","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":"14_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/3-540-36206-1_7","volume-title":"FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science","author":"H-J B\u00f6ckenhauer","year":"2002","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: Agrawal, M., Seth, A. (eds.) FSTTCS 2002. LNCS, vol. 2556, pp. 59\u201370. Springer, Heidelberg (2002). doi:10.1007\/3-540-36206-1_7"},{"key":"14_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/3-540-44849-7_24","volume-title":"Algorithms and Complexity","author":"H-J B\u00f6ckenhauer","year":"2003","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: Petreschi, R., Persiano, G., Silvestri, R. (eds.) CIAC 2003. LNCS, vol. 2653, pp. 189\u2013200. Springer, Heidelberg (2003). doi:10.1007\/3-540-44849-7_24"},{"issue":"4","key":"14_CR8","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. Discret. Algorithms 6(4), 605\u2013617 (2008)","journal-title":"J. Discret. Algorithms"},{"key":"14_CR9","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":"14_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/3-540-46521-9_7","volume-title":"Algorithms and Complexity","author":"H-J B\u00f6ckenhauer","year":"2000","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. In: Bongiovanni, G., Petreschi, R., Gambosi, G. (eds.) CIAC 2000. LNCS, vol. 1767, pp. 72\u201386. Springer, Heidelberg (2000). doi:10.1007\/3-540-46521-9_7"},{"key":"14_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/3-540-46541-3_32","volume-title":"STACS 2000","author":"H-J B\u00f6ckenhauer","year":"2000","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Klasing, R., Seibert, S., Unger, W.: An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inequality. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 382\u2013394. Springer, Heidelberg (2000). doi:10.1007\/3-540-46541-3_32"},{"key":"14_CR12","volume-title":"Handbook of Approximation Algorithms and Metaheuristics","author":"H-J B\u00f6ckenhauer","year":"2007","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Seibert, S.: Stability of approximation. In: Gonzalez, T.F. (ed.) Handbook of Approximation Algorithms and Metaheuristics. Chapman & Hall\/CRC, Boca Raton (2007). Chapter 31"},{"key":"14_CR13","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."},{"key":"14_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":"14_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":"14_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 2016), pp. 13\u201318 (2016)"},{"key":"14_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/978-3-319-42634-1_18","volume-title":"Computing and Combinatorics","author":"L-H Chen","year":"2016","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: Dinh, T.N., Thai, M.T. (eds.) COCOON 2016. LNCS, vol. 9797, pp. 222\u2013234. Springer, Cham (2016). doi:10.1007\/978-3-319-42634-1_18"},{"key":"14_CR18","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":"14_CR19","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"TF Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293\u2013306 (1985)","journal-title":"Theor. Comput. Sci."},{"volume-title":"Approximation Algorithms for NP-hard Problems","year":"1996","key":"14_CR20","unstructured":"Hochbaum, D.S. (ed.): Approximation Algorithms for NP-hard Problems. PWS Publishing Company, Pacific Grove (1996)"},{"key":"14_CR21","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/5925.5933","volume":"33","author":"DS Hochbaum","year":"1986","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A unified approach to approximation algorithms for bottleneck problems. J. ACM 33, 533\u2013550 (1986)","journal-title":"J. ACM"},{"key":"14_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/3-540-47849-3_2","volume-title":"SOFSEM 1999: Theory and Practice of Informatics","author":"J Hromkovi\u010d","year":"1999","unstructured":"Hromkovi\u010d, J.: Stability of approximation algorithms for hard optimization problems. In: Pavelka, J., Tel, G., Barto\u0161ek, M. (eds.) SOFSEM 1999. LNCS, vol. 1725, pp. 29\u201347. Springer, Heidelberg (1999). doi:10.1007\/3-540-47849-3_2"},{"key":"14_CR23","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":"14_CR24","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/j.orl.2012.12.007","volume":"41","author":"H Liang","year":"2013","unstructured":"Liang, H.: The hardness and approximation of the star p-hub center problem. Oper. Res. Lett. 41, 138\u2013141 (2013)","journal-title":"Oper. Res. Lett."},{"key":"14_CR25","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":"14_CR26","first-page":"376","volume":"70","author":"ME O\u2019Kelly","year":"1991","unstructured":"O\u2019Kelly, M.E., Miller, H.J.: Solution strategies for the single facility minimax hub location problem. Pap. Reg. Sci. 70, 376\u2013380 (1991)","journal-title":"Pap. Reg. Sci."},{"key":"14_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11590-015-0867-6","volume":"1","author":"R Todosijevi\u0107","year":"2015","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. Optimization Letters 1, 1\u201313 (2015). doi:10.1007\/s11590-015-0867-6","journal-title":"Optimization Letters"},{"key":"14_CR28","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."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-57586-5_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T14:48:45Z","timestamp":1710341325000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-57586-5_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319575858","9783319575865"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-57586-5_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"14 April 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Athens","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 May 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 May 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.corelab.ntua.gr\/ciac2017\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}