{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:42Z","timestamp":1740122442857,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,12,4]],"date-time":"2024-12-04T00:00:00Z","timestamp":1733270400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,12,4]],"date-time":"2024-12-04T00:00:00Z","timestamp":1733270400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2025,1]]},"DOI":"10.1007\/s10878-024-01237-4","type":"journal-article","created":{"date-parts":[[2024,12,4]],"date-time":"2024-12-04T19:33:41Z","timestamp":1733340821000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximation algorithms for the airport and railway problem"],"prefix":"10.1007","volume":"49","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7650-2045","authenticated-orcid":false,"given":"Mohammad R.","family":"Salavatipour","sequence":"first","affiliation":[]},{"given":"Lijiangnan","family":"Tian","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,12,4]]},"reference":[{"doi-asserted-by":"publisher","unstructured":"Adamaszek A, Antoniadis A, Kumar A, M\u00f6mke T (2018) Approximating airports and railways. In: Niedermeier R, Vall\u00e9e B (eds) 35th symposium on theoretical aspects of computer science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol 96, pp 5\u20131513. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2018.5 . http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/8518","key":"1237_CR1","DOI":"10.4230\/LIPIcs.STACS.2018.5"},{"doi-asserted-by":"publisher","unstructured":"Adamaszek A, Antoniadis A, M\u00f6mke T (2016) Airports and railways: facility location meets network design. In: Ollinger N, Vollmer H (eds) 33rd symposium on theoretical aspects of computer science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol 47, pp 6\u20131614. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2016.6 . http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2016\/5707","key":"1237_CR2","DOI":"10.4230\/LIPIcs.STACS.2016.6"},{"key":"1237_CR3","doi-asserted-by":"publisher","first-page":"258","DOI":"10.2307\/1968431","volume":"35","author":"ET Bell","year":"1934","unstructured":"Bell ET (1934) Exponential polynomials. Ann Math 35:258\u2013277","journal-title":"Ann Math"},{"key":"1237_CR4","doi-asserted-by":"publisher","first-page":"539","DOI":"10.2307\/1968633","volume":"39","author":"ET Bell","year":"1938","unstructured":"Bell ET (1938) The iterated exponential integers. Ann Math 39:539\u2013557","journal-title":"Ann Math"},{"issue":"2","key":"1237_CR5","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/S10107-022-01841-4","volume":"197","author":"J Blauth","year":"2023","unstructured":"Blauth J, Traub V, Vygen J (2023) Improving the approximation ratio for capacitated vehicle routing. Math Program 197(2):451\u2013497. https:\/\/doi.org\/10.1007\/S10107-022-01841-4","journal-title":"Math Program"},{"issue":"6","key":"1237_CR6","doi-asserted-by":"publisher","first-page":"1725","DOI":"10.1137\/S0097539795289859","volume":"27","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender HL, Hagerup T (1998) Parallel algorithms with optimal speedup for bounded treewidth. SIAM J Comput 27(6):1725\u20131746. https:\/\/doi.org\/10.1137\/S0097539795289859","journal-title":"SIAM J Comput"},{"doi-asserted-by":"crossref","unstructured":"Cohen-Addad V, Le H, Pilipczuk M, Pilipczuk M (2023) Planar and minor-free metrics embed into metrics of polylogarithmic treewidth with expected multiplicative distortion arbitrarily close to $$1$$. In: 2023 IEEE 64th annual symposium on foundations of computer science (FOCS)","key":"1237_CR7","DOI":"10.1109\/FOCS57990.2023.00140"},{"doi-asserted-by":"publisher","unstructured":"Das A, Mathieu C (2010) A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing. In: Charikar M (ed) Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, Texas, USA, January 17\u201319, 2010, pp 390\u2013403. SIAM. https:\/\/doi.org\/10.1137\/1.9781611973075.33","key":"1237_CR8","DOI":"10.1137\/1.9781611973075.33"},{"key":"1237_CR9","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0167-5060(08)70817-3","volume-title":"Discrete optimization I. Annals of discrete mathematics","author":"J Edmonds","year":"1979","unstructured":"Edmonds J (1979) Matroid intersection. In: Hammer PL, Johnson EL, Korte BH (eds) Discrete optimization I. Annals of discrete mathematics, vol 4. Elsevier, Amsterdam, pp 39\u201349. https:\/\/doi.org\/10.1016\/S0167-5060(08)70817-3"},{"issue":"4","key":"1237_CR10","doi-asserted-by":"publisher","first-page":"1667","DOI":"10.1137\/16m1067196","volume":"47","author":"AE Feldmann","year":"2018","unstructured":"Feldmann AE, Fung WS, K\u00f6nemann J, Post I (2018) A $$ (1+\\epsilon ) $$-embedding of low highway dimension graphs into bounded treewidth graphs. SIAM J Comput 47(4):1667\u20131704. https:\/\/doi.org\/10.1137\/16m1067196","journal-title":"SIAM J Comput"},{"doi-asserted-by":"publisher","unstructured":"Friggstad Z, Mousavi R, Rahgoshay M, Salavatipour MR (2022) Improved approximations for capacitated vehicle routing with unsplittable client demands. In: Aardal KI, Sanit\u00e0 L (eds) Integer programming and combinatorial optimization-23rd international conference, IPCO 2022, Eindhoven, The Netherlands, June 27\u201329, 2022, Proceedings. Lecture Notes in Computer Science, 13265, pp 251\u2013261. Springer . https:\/\/doi.org\/10.1007\/978-3-031-06901-7_19","key":"1237_CR11","DOI":"10.1007\/978-3-031-06901-7_19"},{"issue":"2","key":"1237_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3582500","volume":"19","author":"A Jayaprakash","year":"2023","unstructured":"Jayaprakash A, Salavatipour MR (2023) Approximation schemes for capacitated vehicle routing on graphs of bounded treewidth, bounded doubling, or highway dimension. ACM Trans Algorithms 19(2):1\u201336. https:\/\/doi.org\/10.1145\/3582500","journal-title":"ACM Trans Algorithms"},{"issue":"2","key":"1237_CR13","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1145\/1103963.1103967","volume":"1","author":"R Jothi","year":"2005","unstructured":"Jothi R, Raghavachari B (2005) Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design. ACM Trans Algorithms 1(2):265\u2013282. https:\/\/doi.org\/10.1145\/1103963.1103967","journal-title":"ACM Trans Algorithms"},{"unstructured":"Kao M-J (2021) Improved LP-based approximation algorithms for facility location with hard capacities. arXiv preprint arXiv:2102.06613","key":"1237_CR14"},{"issue":"2","key":"1237_CR15","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/S00453-012-9740-5","volume":"69","author":"MR Khani","year":"2014","unstructured":"Khani MR, Salavatipour MR (2014) Improved approximation algorithms for the min-max tree cover and bounded tree cover problems. Algorithmica 69(2):443\u2013460. https:\/\/doi.org\/10.1007\/S00453-012-9740-5","journal-title":"Algorithmica"},{"issue":"4","key":"1237_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1383369.1383381","volume":"4","author":"J Ma\u00dfberg","year":"2008","unstructured":"Ma\u00dfberg J, Vygen J (2008) Approximation algorithms for a facility location problem with service capacities. ACM Trans Algorithms 4(4):1\u201315. https:\/\/doi.org\/10.1145\/1383369.1383381","journal-title":"ACM Trans Algorithms"},{"issue":"2","key":"1237_CR17","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/3575799","volume":"19","author":"C Mathieu","year":"2023","unstructured":"Mathieu C, Zhou H (2023) A PTAS for capacitated vehicle routing on trees. ACM Trans Algorithms 19(2):17\u201311728. https:\/\/doi.org\/10.1145\/3575799","journal-title":"ACM Trans Algorithms"},{"key":"1237_CR18","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.tcs.2022.08.002","volume":"932","author":"R Miao","year":"2022","unstructured":"Miao R, Yuan J (2022) A note on LP-based approximation algorithms for capacitated facility location problem. Theoret Comput Sci 932:31\u201340. https:\/\/doi.org\/10.1016\/j.tcs.2022.08.002","journal-title":"Theoret Comput Sci"},{"issue":"1","key":"1237_CR19","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1287\/opre.1050.0228","volume":"54","author":"R Ravi","year":"2006","unstructured":"Ravi R, Sinha A (2006) Approximation algorithms for problems combining facility location and network design. Oper Res 54(1):73\u201381","journal-title":"Oper Res"},{"doi-asserted-by":"publisher","unstructured":"Talwar K (2004) Bypassing the embedding: algorithms for low dimensional metrics. In: Proceedings of the thirty-sixth annual ACM symposium on theory of computing. STOC \u201904, pp 281\u2013290. Association for Computing Machinery, New York, NY, USA. https:\/\/doi.org\/10.1145\/1007352.1007399","key":"1237_CR20","DOI":"10.1145\/1007352.1007399"},{"unstructured":"Tian L (2023) Approximation schemes for the airport and railway problem. Master\u2019s thesis, Department of Computing Science, Faculty of Science, University of Alberta","key":"1237_CR21"},{"issue":"1","key":"1237_CR22","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/S10107-021-01678-3","volume":"192","author":"V Traub","year":"2022","unstructured":"Traub V, Tr\u00f6bst T (2022) A fast $$(2 + \\frac{2}{7})$$-approximation algorithm for capacitated cycle covering. Math Progr 192(1):497\u2013518. https:\/\/doi.org\/10.1007\/S10107-021-01678-3","journal-title":"Math Progr"},{"key":"1237_CR23","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/J.TCS.2019.04.009","volume":"793","author":"W Yu","year":"2019","unstructured":"Yu W, Liu Z, Bao X (2019) New approximation algorithms for the minimum cycle cover problem. Theoret Comput Sci 793:44\u201358. https:\/\/doi.org\/10.1016\/J.TCS.2019.04.009","journal-title":"Theoret Comput Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01237-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01237-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01237-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T19:03:25Z","timestamp":1737745405000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01237-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,4]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["1237"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01237-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,12,4]]},"assertion":[{"value":"29 October 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 December 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"There are no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"8"}}