{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T07:35:03Z","timestamp":1790667303078,"version":"4.1.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T00:00:00Z","timestamp":1558051200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T00:00:00Z","timestamp":1558051200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11531014"],"award-info":[{"award-number":["11531014"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2021,10]]},"DOI":"10.1007\/s10878-019-00418-w","type":"journal-article","created":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T07:05:28Z","timestamp":1558076728000},"page":"499-523","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Algorithms for the metric ring star problem with fixed edge-cost ratio"],"prefix":"10.1007","volume":"42","author":[{"given":"Xujin","family":"Chen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaodong","family":"Hu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaohua","family":"Jia","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhongzheng","family":"Tang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2481-5648","authenticated-orcid":false,"given":"Chenhao","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,5,17]]},"reference":[{"key":"418_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal A, Klein P, Ravi R (1995) When trees collide: an approximation algorithm for the generalized Steiner problem on networks. In: ACM symposium on theory of computing, pp 134\u2013144","DOI":"10.1137\/S0097539792236237"},{"issue":"1","key":"418_CR2","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/j.ejor.2009.07.026","volume":"203","author":"R Baldacci","year":"2010","unstructured":"Baldacci R, DellAmico M (2010) Heuristic algorithms for the multi-depot ring-star problem. Eur J Oper Res 203(1):270\u2013281","journal-title":"Eur J Oper Res"},{"issue":"6","key":"418_CR3","doi-asserted-by":"publisher","first-page":"1147","DOI":"10.1287\/opre.1070.0432","volume":"55","author":"R Baldacci","year":"2007","unstructured":"Baldacci R, DellAmico M, Gonz\u00e1lez JS (2007) The capacitated m-ring-star problem. Oper Res 55(6):1147\u20131162","journal-title":"Oper Res"},{"issue":"1","key":"418_CR4","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF02568604","volume":"4","author":"JE Beasley","year":"1996","unstructured":"Beasley JE, Nascimento EM (1996) The vehicle routing-allocation problem: a unifying framework. Top 4(1):65\u201386","journal-title":"Top"},{"key":"418_CR5","volume-title":"Combinatorial optimization: theory and algorithms","author":"K Bernhard","year":"2008","unstructured":"Bernhard K, Vygen J (2008) Combinatorial optimization: theory and algorithms, vol 3. Springer, Berlin 2005"},{"key":"418_CR6","doi-asserted-by":"crossref","unstructured":"Byrka J, Grandoni F (2010) An improved lp-based approximation for Steiner tree. In: ACM symposium on theory of computing, pp 583\u2013592","DOI":"10.1145\/1806689.1806769"},{"issue":"1","key":"418_CR7","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.ejor.2013.05.013","volume":"231","author":"HI Calvete","year":"2013","unstructured":"Calvete HI, Gal\u00e9 C, Iranzo JA (2013) An efficient evolutionary algorithm for the ring star problem. Eur J Oper Res 231(1):22\u201333","journal-title":"Eur J Oper Res"},{"issue":"2","key":"418_CR8","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1016\/j.ejor.2015.09.044","volume":"250","author":"HI Calvete","year":"2016","unstructured":"Calvete HI, Gale C, Iranzo JA (2016) Meals: a multiobjective evolutionary algorithm with local search for solving the bi-objective ring star problem. Eur J Oper Res 250(2):377\u2013388","journal-title":"Eur J Oper Res"},{"key":"418_CR9","doi-asserted-by":"crossref","unstructured":"Chen X, Hu X, Tang Z, Wang C, Zhang Y (2017) Algorithms for the ring star problem. In: International conference on combinatorial optimization and applications, pp 3\u201316","DOI":"10.1007\/978-3-319-71147-8_1"},{"key":"418_CR10","unstructured":"Christofides N (1976) Worst-case analysis of a new heuristic for the traveling salesman problem"},{"issue":"6","key":"418_CR11","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1287\/opre.6.6.791","volume":"6","author":"GA Croes","year":"1958","unstructured":"Croes GA (1958) A method for solving traveling-salesman problems. Oper Res 6(6):791\u2013812","journal-title":"Oper Res"},{"issue":"94","key":"418_CR12","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/0377-2217(94)90149-X","volume":"73","author":"JR Current","year":"1994","unstructured":"Current JR, Schilling DA (1994) The median tour and maximal covering tour problems: formulations and heuristics. Eur J Oper Res 73(94):114\u2013126","journal-title":"Eur J Oper Res"},{"key":"418_CR13","doi-asserted-by":"crossref","unstructured":"Dias TCS, de\u00a0Sousa\u00a0Filho GF, Macambira EM, Lucidio\u00a0dos Anjos FC, Fampa MHC (2006) An efficient heuristic for the ring star problem. In: International workshop on experimental and efficient algorithms, Springer, pp 24\u201335","DOI":"10.1007\/11764298_3"},{"issue":"8","key":"418_CR14","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1016\/j.jcss.2010.02.001","volume":"76","author":"F Eisenbrand","year":"2010","unstructured":"Eisenbrand F, Grandoni F, Rothvoi T, Schafer G (2010) Connected facility location via random facility sampling and core detouring. J Comput Syst Sci 76(8):709\u2013726","journal-title":"J Comput Syst Sci"},{"issue":"2","key":"418_CR15","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1006\/jagm.1997.0862","volume":"24","author":"SP Fekete","year":"1997","unstructured":"Fekete SP, Khuller S, Klemmstein M, Raghavachari B, Young N (1997) A network-flow technique for finding low-weight bounded-degree spanning trees. J Algorithms 24(2):310\u2013324","journal-title":"J Algorithms"},{"key":"418_CR16","doi-asserted-by":"crossref","unstructured":"Gupta A, Kumar A, Roughgarden T (2003) Simpler and better approximation algorithms for network design. In: STOC, pp 365\u2013372","DOI":"10.1145\/780542.780597"},{"key":"418_CR17","doi-asserted-by":"crossref","unstructured":"Held M, Karp RM (1961) A dynamic programming approach to sequencing problems. In: International business machines corporation, pp 196\u2013210","DOI":"10.1145\/800029.808532"},{"issue":"2","key":"418_CR18","first-page":"1","volume":"4","author":"A Hill","year":"2017","unstructured":"Hill A, Vob S (2017) Optimal capacitated ring trees. Euro J Comput Optim 4(2):1\u201330","journal-title":"Euro J Comput Optim"},{"key":"418_CR19","doi-asserted-by":"crossref","unstructured":"Hromkovic J, Klasing R, Seibert S, Unger W (2000) An improved lower bound on the approximability of metric tsp and approximation algorithms for the tsp with sharpened triangle inequality. In: Symposium on theoretical aspects of computer science, pp 382\u2013394","DOI":"10.1007\/3-540-46541-3_32"},{"issue":"3","key":"418_CR20","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1287\/mnsc.14.3.205","volume":"14","author":"M Klein","year":"1967","unstructured":"Klein M (1967) A primal method for minimal cost flows with applications to the assignment and transportation problems. Manag Sci 14(3):205\u2013220","journal-title":"Manag Sci"},{"issue":"3","key":"418_CR21","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1002\/net.10114","volume":"43","author":"M Labb\u00e9","year":"2004","unstructured":"Labb\u00e9 M, Laporte G, Mart\u00edn IR, Gonz\u00e1lez JJS (2004) The ring star problem: polyhedral analysis and exact algorithm. Networks 43(3):177\u2013189","journal-title":"Networks"},{"issue":"6","key":"418_CR22","doi-asserted-by":"publisher","first-page":"1033","DOI":"10.1016\/j.cor.2009.09.004","volume":"37","author":"A Liefooghe","year":"2010","unstructured":"Liefooghe A, Jourdan L, Talbi EG (2010) Metaheuristics and cooperative approaches for the bi-objective ring star problem. Comput Oper Res 37(6):1033\u20131044","journal-title":"Comput Oper Res"},{"issue":"2","key":"418_CR23","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/S0377-2217(02)00831-7","volume":"151","author":"JAM P\u00e9rez","year":"2003","unstructured":"P\u00e9rez JAM, Moreno-Vega JM, Mart\u0131n IR (2003) Variable neighborhood tabu search and its application to the median cycle problem. Eur J Oper Res 151(2):365\u2013378","journal-title":"Eur J Oper Res"},{"key":"418_CR24","first-page":"29","volume-title":"Approximation algorithms for the traveling purchaser problem and its variants in network design","author":"R Ravi","year":"1999","unstructured":"Ravi R, Salman FS (1999) Approximation algorithms for the traveling purchaser problem and its variants in network design. Springer, Berlin, pp 29\u201340"},{"issue":"4","key":"418_CR25","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G Reinelt","year":"1991","unstructured":"Reinelt G (1991) Tsplib: a traveling salesman problem library. ORSA J Comput 3(4):376\u2013384","journal-title":"ORSA J Comput"},{"issue":"1","key":"418_CR26","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/S0895480101393155","volume":"19","author":"G Robins","year":"2005","unstructured":"Robins G, Zelikovsky A (2005) Tighter bounds for graph steiner tree approximation. Siam J Discrete Math 19(1):122\u2013134","journal-title":"Siam J Discrete Math"},{"issue":"16","key":"418_CR27","doi-asserted-by":"publisher","first-page":"1901","DOI":"10.1016\/j.dam.2011.01.015","volume":"159","author":"L Simonetti","year":"2011","unstructured":"Simonetti L, Frota Y, de Souza CC (2011) The ring-star problem: a new integer programming formulation and a branch-and-cut algorithm. Discrete Appl Math 159(16):1901\u20131914","journal-title":"Discrete Appl Math"},{"issue":"4","key":"418_CR28","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00453-004-1112-3","volume":"40","author":"C Swamy","year":"2004","unstructured":"Swamy C, Kumar A (2004) Primal-dual algorithms for connected facility location problems. Algorithmica 40(4):245\u2013269","journal-title":"Algorithmica"},{"key":"418_CR29","volume-title":"Approximation algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani VV (2001) Approximation algorithms. Springer, Berlin"},{"issue":"6","key":"418_CR30","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1016\/j.orl.2007.02.005","volume":"35","author":"DP Williamson","year":"2007","unstructured":"Williamson DP, Van Zuylen A (2007) A simpler and better derandomization of an approximation algorithm for single source rent-or-buy. Oper Res Lett 35(6):707\u2013712","journal-title":"Oper Res Lett"},{"issue":"3","key":"418_CR31","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1287\/mnsc.45.3.330","volume":"45","author":"J Xu","year":"1999","unstructured":"Xu J, Chiu SY, Glover F (1999) Optimizing a ring-based private line telecommunication network using tabu search. Manag Sci 45(3):330\u2013345","journal-title":"Manag Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00418-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-019-00418-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00418-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T06:31:19Z","timestamp":1635575479000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-019-00418-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,17]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["418"],"URL":"https:\/\/doi.org\/10.1007\/s10878-019-00418-w","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,17]]},"assertion":[{"value":"17 May 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}