{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:37Z","timestamp":1740109417524,"version":"3.37.3"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,2,2]],"date-time":"2017-02-02T00:00:00Z","timestamp":1485993600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["311499\/2014-7"],"award-info":[{"award-number":["311499\/2014-7"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["477692\/2012-5"],"award-info":[{"award-number":["477692\/2012-5"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["2014\/14209-1"],"award-info":[{"award-number":["2014\/14209-1"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["2013\/21744-8"],"award-info":[{"award-number":["2013\/21744-8"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,10]]},"DOI":"10.1007\/s00224-017-9749-x","type":"journal-article","created":{"date-parts":[[2017,2,1]],"date-time":"2017-02-01T23:52:59Z","timestamp":1485993179000},"page":"871-892","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A PTAS for the Geometric Connected Facility Location Problem"],"prefix":"10.1007","volume":"61","author":[{"given":"Fl\u00e1vio K.","family":"Miyazawa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lehilton L.","family":"C. Pedrosa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rafael C.","family":"S. Schouery","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Renata G.","family":"D. de Souza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,2,2]]},"reference":[{"key":"9749_CR1","doi-asserted-by":"publisher","unstructured":"Arora, S.: Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and Other Geometric Problems. J. ACM 45(5), 753\u2013782 (1998). doi:\n                        10.1145\/290179.290180","DOI":"10.1145\/290179.290180"},{"key":"9749_CR2","doi-asserted-by":"publisher","unstructured":"Arora, S., Raghavan, P., Rao, S.: Approximation Schemes for Euclidean K-medians and Related Problems. In: Proc.of the 30th Annual ACM Symposium on Theory of Computing, pp. 106\u2013113. ACM. doi:\n                        10.1145\/276698.276718\n                        \n                    (1998)","DOI":"10.1145\/276698.276718"},{"issue":"3-4","key":"9749_CR3","doi-asserted-by":"publisher","first-page":"906","DOI":"10.1007\/s00453-011-9491-8","volume":"62","author":"M Bateni","year":"2012","unstructured":"Bateni, M., Hajiaghayi, M.: Euclidean Prize-Collecting Steiner Forest. Algorithmica 62(3-4), 906\u2013929 (2012). doi:\n                        10.1007\/s00453-011-9491-8","journal-title":"Algorithmica"},{"issue":"3","key":"9749_CR4","doi-asserted-by":"publisher","first-page":"19:1","DOI":"10.1145\/2629654","volume":"11","author":"G Borradaile","year":"2015","unstructured":"Borradaile, G., Klein, P.N., Mathieu, C.: A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. ACM Trans. Algorithm. 11(3), 19:1\u201319:20 (2015). doi:\n                        10.1145\/2629654","journal-title":"ACM Trans. Algorithm."},{"key":"9749_CR5","doi-asserted-by":"crossref","unstructured":"Das, A., Mathieu, C.: A Quasi-Polynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing. In: Proc.Of the 21St Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 390\u2013403 (2010)","DOI":"10.1137\/1.9781611973075.33"},{"issue":"1-6","key":"9749_CR6","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BF01758755","volume":"7","author":"DZ Du","year":"1992","unstructured":"Du, D.Z., Hwang, F.: A proof of the Gilbert-Pollak conjecture on the Steiner ratio. Algorithmica 7(1-6), 121\u2013135 (1992). doi:\n                        10.1007\/BF01758755","journal-title":"Algorithmica"},{"key":"9749_CR7","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman (1979)"},{"issue":"1","key":"9749_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0116001","volume":"16","author":"EN Gilbert","year":"1968","unstructured":"Gilbert, E.N., Pollak, H.O.: Steiner minimal trees. SIAM J. Appl. Math. 16(1), 1\u201329 (1968). doi:\n                        10.1137\/0116001","journal-title":"SIAM J. Appl. Math."},{"issue":"2","key":"9749_CR9","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: A General Approximation Technique for Constrained Forest Problems. SIAM J. Comput. 24(2), 296\u2013317 (1995). doi:\n                        10.1137\/S0097539793242618","journal-title":"SIAM J. Comput."},{"key":"9749_CR10","doi-asserted-by":"publisher","unstructured":"Gupta, A., Kleinberg, J., Kumar, A., Rastogi, R., Yener, B.: Provisioning a Virtual Private Network: A Network Design Problem for Multicommodity Flow. In: Proc.of the 33th Annual ACM Symposium on Theory of Computing, pp. 389\u2013398. doi:\n                        10.1145\/380752.380830\n                        \n                     (2001)","DOI":"10.1145\/380752.380830"},{"issue":"1","key":"9749_CR11","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/0402010","volume":"2","author":"HJ Karloff","year":"1989","unstructured":"Karloff, H.J.: How Long Can a Euclidean Traveling Salesman Tour Be? SIAM J. Discret. Math. 2(1), 91\u201399 (1989). doi:\n                        10.1137\/0402010","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"9749_CR12","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1137\/S0097539702404055","volume":"37","author":"SG Kolliopoulos","year":"2007","unstructured":"Kolliopoulos, S.G., Rao, S.: A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem. SIAM J. Comput. 37(3), 757\u2013782 (2007). doi:\n                        10.1137\/S0097539702404055","journal-title":"SIAM J. Comput."},{"key":"9749_CR13","doi-asserted-by":"crossref","unstructured":"Meira, L.A.A., Miyazawa, F.K.: A Continuous Facility Location Problem and Its Application to a Clustering Problem. In: Proc.Of the 2008 ACM Symposium on Applied Computing. pp. 1826\u20131831 (2008)","DOI":"10.1145\/1363686.1364126"},{"issue":"4","key":"9749_CR14","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"JSB Mitchell","year":"1999","unstructured":"Mitchell, J.S.B.: Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems. SIAM J. Comput. 28(4), 1298\u20131309 (1999). doi:\n                        10.1137\/S0097539796309764","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9749_CR15","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/s00453-007-9114-6","volume":"55","author":"J Remy","year":"2007","unstructured":"Remy, J., Steger, A.: Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems. Algorithmica 55(1), 240\u2013267 (2007). doi:\n                        10.1007\/s00453-007-9114-6","journal-title":"Algorithmica"},{"key":"9749_CR16","doi-asserted-by":"publisher","unstructured":"Shmoys, D.B., Tardos, E., Aardal, K.: Approximation Algorithms for Facility Location Problems (Extended Abstract). In: Proc.of the 39th Annual ACM Symposium on Theory of Computing. pp. 265\u2013274. doi:\n                        10.1145\/258533.258600\n                        \n                    (1997)","DOI":"10.1145\/258533.258600"},{"issue":"4","key":"9749_CR17","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.: Primal-Dual Algorithms for Connected Facility Location Problems. Algorithmica 40(4), 245\u2013269 (2004). doi:\n                        10.1007\/s00453-004-1112-3","journal-title":"Algorithmica"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9749-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9749-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9749-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,8,16]],"date-time":"2017-08-16T04:04:50Z","timestamp":1502856290000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9749-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,2]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["9749"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9749-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2017,2,2]]}}}