{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T23:40:08Z","timestamp":1737502808245,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540405344"},{"type":"electronic","value":"9783540450719"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45071-8_6","type":"book-chapter","created":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T08:04:43Z","timestamp":1193472283000},"page":"40-49","source":"Crossref","is-referenced-by-count":0,"title":["Traveling Salesman Problem of Segments"],"prefix":"10.1007","author":[{"given":"Jinhui","family":"Xu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhiyong","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,24]]},"reference":[{"key":"6_CR1","unstructured":"E. M. Arkin, Y.-J. Chiang, J. S. B. Mitchell, S. S. Skiena, and T. Yang. On the maximum scatter TSP, Proc. 8th ACM-SIAM Sympos. Discrete Algorithms, pp. 211\u2013220, 1997."},{"key":"6_CR2","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0166-218X(94)90008-6","volume":"55","author":"E. M. Arkin","year":"1994","unstructured":"E. M. Arkin and R. Hassin, Approximation algorithms for the geometric covering salesman problem, Discrete Appl. Math., 55:197\u2013218, 1994.","journal-title":"Discrete Appl. Math."},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"E. M. Arkin, J. S. B. Mitchell, and G. Narasimhan, Resource-constrained geometric network optimization, Proc. 14th Annu. ACM Sympos. Comput. Geom., pp. 419\u2013428, 1998.","DOI":"10.1145\/276884.276919"},{"key":"6_CR4","unstructured":"S. Arora, M. Grigni, D. Karger, P. Klein, and A. Woloszyn, Polynomial Time Approximation Scheme for Weighted Planar Graph TSP, Proc. 9th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pp. 33\u201341, 1998."},{"issue":"5","key":"6_CR5","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"S. Arora, Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM, 45(5) pp. 753\u2013782, 1998.","journal-title":"Journal of the ACM"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Y. Azar, A. Blum, and S. Vempala, Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesman, Proc. 27th Annu. ACM Sympos. Theory Comput., pp. 277\u2013283, 1995.","DOI":"10.1145\/225058.225139"},{"key":"6_CR7","unstructured":"A. Blum, P. Chalasani, D. Coppersmith, B. Pulleyblank, P. Raghavan, and M. Sudan, The minimum latency problem, Proc. 26th Annu. ACM Sympos. Theory Comput. (STOC 94), pp. 16"},{"key":"6_CR8","volume-title":"Approximating the shortest watchman route in a simple polygon","author":"S. Carlsson","year":"1997","unstructured":"S. Carlsson, H. Jonsson, and B. J. Nilsson, Approximating the shortest watchman route in a simple polygon. Manuscript, Dept. Comput. Sci., Lund Univ., Lund, Sweden, 1997."},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"D.Z. Chen, O. Daescu, X. Hu, X. Wu, and J. Xu, Determining an Optimal Penetration among Weighted Regions in 2 and 3 Dimensions, SCG\u201999, pp. 322\u2013331.","DOI":"10.1145\/304893.304986"},{"issue":"3","key":"6_CR10","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1023\/A:1011497227406","volume":"5","author":"X. Cheng","year":"2001","unstructured":"X. Cheng, J. Kim, and B. Lu, A Polynomial Time Approx. Scheme for the problem of Interconnecting Highways, J. of Combin. Optim., Vol.5(3), pp. 327\u2013343, 2001.","journal-title":"J. of Combin. Optim."},{"issue":"4","key":"6_CR11","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1287\/ijoc.4.4.387","volume":"4","author":"J.L. Bentley","year":"1992","unstructured":"J.L. Bentley, Fast Algorithms for Geometric Traveling Salesman Problems, ORSA J. Comput., 4(4):387\u2013411, 1992.","journal-title":"ORSA J. Comput."},{"key":"6_CR12","first-page":"441","volume-title":"Symposium on New Directions and Recent Results in Algorithms and Complexity","author":"N. Christofides","year":"1976","unstructured":"N. Christofides, Worst-case analysis of a new heuristic for the traveling salesman problem, In J.F. Traub, editor, Symposium on New Directions and Recent Results in Algorithms and Complexity, Academic Press, NY, pp. 441, 1976."},{"key":"6_CR13","unstructured":"A. Dumitrescu and J.S.B. Mitchell, Approximation algorithms for TSP with neighborhoods in the plane, Proc. 12th ACM-SIAM Sympos. Discrete Algorithms (SODA\u20192001), pp. 38\u201346, 2001."},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"N. Garg, A 3-approximation for the minimum tree spanning k vertices, 37th Annual Symposium on Foundations of Computer Science, pp. 302\u2013309, Burlington, Vermont, October 14\u201316 1996.","DOI":"10.1109\/SFCS.1996.548489"},{"key":"6_CR15","unstructured":"M. X. Goemans and J. M. Kleinberg, An improved approximation ratio for the minimum latency problem, Proc. 7th ACM-SIAM Sympos. Discrete Algorithms (SODA\u2019 96), pp. 152\u2013158, 1996."},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"M. Grigni, E. Koutsoupias, and C.H. Papadimitriou, An Approximation Scheme for Planar Graph TSP, Proc. IEEE Symposium on Foundations of Computer Science, pp. 640\u2013645, 1995.","DOI":"10.1109\/SFCS.1995.492665"},{"key":"6_CR17","unstructured":"J. Gudmundsson and C. Levcopoulos, A fast approxmation algorithm for TSP with neighborhoods. Technical Report LU-CS-TR:97-195, Dept. of Comp. Sci., Lund University, 1997."},{"key":"6_CR18","unstructured":"R. Hassin and S. Rubinstein, An approximation algorithm for the maximum traveling salesman problem. Manuscript, submitted, Tel Aviv University, Tel Aviv, Israel, 1997."},{"key":"6_CR19","series-title":"Handbook of Operations Research\/Management Science","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/S0927-0507(05)80121-5","volume-title":"Network Models","author":"M. J\u00fcnger","year":"1995","unstructured":"M. J\u00fcnger, G. Reinelt, and G. Rinaldi, The Traveling Salesman Problem. In M. O. Ball, T.L. Magnanti, C. L. Monma, and G. L. Nemhauser, editors, Network Models, Handbook of Operations Research\/Management Science, Elsevier Science, Amsterdam, pp. 225\u2013330, 1995."},{"key":"6_CR20","unstructured":"S. Kosaraju, J. Park, and C. Stein, Long tours and short superstrings, Proc. 35th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS 94), 1994."},{"volume-title":"The Traveling Salesman Problem","year":"1985","key":"6_CR21","unstructured":"E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys, editors. The Traveling Salesman Problem, Wiley, New York, NY, 1985."},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"C. Mata and J. S. B. Mitchell, Approximation algorithms for geometric tour and network design problems, Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 360\u2013369, 1995.","DOI":"10.1145\/220279.220318"},{"key":"6_CR23","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"J.S.B. Mitchell","year":"1999","unstructured":"J.S.B. Mitchell, Guillotine Subdivisions Approximate Polygonal Subdivisions: Part II \u2014 A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems, SIAM J. Computing, Vol.28, No. 4, pp. 1298\u20131309, 1999.","journal-title":"SIAM J. Computing"},{"key":"6_CR24","unstructured":"J.S.B. Mitchell, Guillotine Subdivisions Approximate Polygonal Subdivisions: Part III \u2014 Faster Polynomial-time Approximation Schemes for Geometric Network Optimization, Manuscript, April 1997."},{"key":"6_CR25","doi-asserted-by":"crossref","unstructured":"J.S.B. Mitchell, Geometric Shortest Paths and Network Optimization, chapter in Handbook of Computational Geometry, Elsevier Science, (J.-R. Sack and J. Urrutia, eds.), 2000.","DOI":"10.1016\/B978-044482537-7\/50016-4"},{"key":"6_CR26","doi-asserted-by":"crossref","unstructured":"S.B. Rao, and W.D. Smith, Improved Approximation Schemes for Geometrical Graphs via \u201cspanners\u201d and \u201cbanyans\u201d Proc. 30th Annu. ACM Sympos. Theory Comput., May 1998.","DOI":"10.1145\/276698.276868"},{"key":"6_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C.H. Papadimitriou","year":"1993","unstructured":"C.H. Papadimitriou and M. Yannakakis, The Traveling Salesman Problem with Distances One and Two, Mathematics of Operations Research, Vol. 18, pp. 1\u201311, 1993.","journal-title":"Mathematics of Operations Research"},{"key":"6_CR28","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1287\/ijoc.4.2.206","volume":"4","author":"G. Reinelt","year":"1992","unstructured":"G. Reinelt, Fast Heuristics for Large Geometric Traveling Salesman Problems, ORSA J. Comput., 4:206\u2013217, 1992.","journal-title":"ORSA J. Comput."},{"issue":"6","key":"6_CR29","doi-asserted-by":"publisher","first-page":"764","DOI":"10.1109\/70.265920","volume":"9","author":"A. Schweikard","year":"1993","unstructured":"A. Schweikard, J.R. Adler, and J.C. Latombe, Motion Planning in Stereotaxic Radiosurgery, IEEE Trans. on Robotics and Automation, Vol. 9, No. 6, pp. 764\u2013774, 1993.","journal-title":"IEEE Trans. on Robotics and Automation"},{"key":"6_CR30","volume-title":"Corrigendum to \u2018An incremental algorithm for constructing shortest watchman routes\u2019","author":"X. Tan","year":"1998","unstructured":"X. Tan, T. Hirata, and Y. Inagaki, Corrigendum to \u2018An incremental algorithm for constructing shortest watchman routes\u2019. Manuscript (submitted to internat. j.comput.geom.appl.), Tokai University, Japan, 1998."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45071-8_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T23:25:56Z","timestamp":1737501956000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45071-8_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405344","9783540450719"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-45071-8_6","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}