{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T06:47:49Z","timestamp":1765176469245},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422259"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/3-540-45535-3_32","type":"book-chapter","created":{"date-parts":[[2010,2,11]],"date-time":"2010-02-11T14:39:51Z","timestamp":1265899191000},"page":"406-421","source":"Crossref","is-referenced-by-count":10,"title":["Approximation Algorithms for the Minimum Bends Traveling Salesman Problem"],"prefix":"10.1007","author":[{"given":"Clifford","family":"Stein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David P.","family":"Wagner*","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"32_CR1","doi-asserted-by":"crossref","unstructured":"F. Afrati, S. Cosmadakis, C. Papadimitriou, G. Papageorgiou, and N. Papakostantinou. The complexity of the travelling repairman problem. Informatique Theoretique et Applications, pages 79\u201387, 1986.","DOI":"10.1051\/ita\/1986200100791"},{"issue":"3","key":"32_CR2","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1137\/S0097539796312721","volume":"29","author":"A. Aggarwal","year":"2000","unstructured":"Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, and Baruch Schieber. The angular-metric traveling salesman problem. SIAM Journal on Computing, 29(3):697\u2013711, June 2000.","journal-title":"SIAM Journal on Computing"},{"key":"32_CR3","unstructured":"Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sandor P. Fekete, Joseph S. B. Mitchell, and Saurabh Sethia. Optimal covering tours with turn costs. In Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms, pages 138\u2013147, Washington, DC, 2001."},{"key":"32_CR4","unstructured":"Esther M. Arkin, Yi-Jen Chiang, Joseph S. B. Mitchell, Steven S. Skiena, and Tae-Cheon Yang. On the maximum scatter TSP (extended abstract). In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 211\u2013220, New Orleans, Louisiana, 5\u20137 January 1997."},{"key":"32_CR5","doi-asserted-by":"crossref","unstructured":"S. Arora. Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. JACM: Journal of the ACM 45, 1998.","DOI":"10.1145\/290179.290180"},{"key":"32_CR6","doi-asserted-by":"crossref","unstructured":"A. Barvinok, Sandor P. Fekete, David S. Johnson, Arie Tamir, Gerhard J. Woeginger, and D. Woodroofe. The maximum traveling salesman problem. submitted to Journal of Algorithms, 1998.","DOI":"10.1007\/3-540-69346-7_15"},{"key":"32_CR7","doi-asserted-by":"crossref","unstructured":"A. Blum, P. Chasalani, D. Coppersmith, B. Pulleyblank, P. Raghavan, and M. Sudan. The minimum latency problem. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 163\u2013172, May 1994.","DOI":"10.1145\/195058.195125"},{"key":"32_CR8","first-page":"263","volume":"14","author":"H. Bronnimann","year":"1995","unstructured":"H. Bronnimann and M.T. Goodrich. Almost optimal set covers infinite VC-dimension. Discrete Computat. Geom., 14:263\u2013279, 1995.","journal-title":"Discrete Computat. Geom."},{"key":"32_CR9","volume-title":"Technical report","author":"N. Christofedes","year":"1976","unstructured":"N. Christofedes. Worst case analysis of a new heuristc for the traveling salesman problem. Technical report, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA, 1976."},{"issue":"3","key":"32_CR10","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"V. Chv\u00e1tal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3):233\u2013235, August 1979.","journal-title":"Mathematics of Operations Research"},{"key":"32_CR11","doi-asserted-by":"crossref","unstructured":"R. Duh and M. Furer. Approximation of k-set cover by semi-local optimization. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 256\u2013264, 1997.","DOI":"10.1145\/258533.258599"},{"issue":"4","key":"32_CR12","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1287\/opre.27.4.799","volume":"27","author":"M. L. Fisher","year":"1979","unstructured":"M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey. An analysis of approximations for finding a maximum weight hamiltonian circuit. Operations Research, 27(4):799\u2013809, July-August 1979.","journal-title":"Operations Research"},{"issue":"7","key":"32_CR13","first-page":"41","volume":"25","author":"R.S. Garfinkel","year":"1977","unstructured":"R.S. Garfinkel. Minimizing wallpaper waste, part I: a class of traveling salesman problems. Operations Research, 257:41\u2013751, 1977.","journal-title":"Operations Research"},{"key":"32_CR14","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1287\/opre.12.5.655","volume":"12","author":"P.C. Gilmore","year":"1964","unstructured":"P.C. Gilmore and R.E. Gomory. Sequencing a one state-variable machine: a solvable case of the traveling salesman problem. Operations Research, 12:655\u2013679, 1964.","journal-title":"Operations Research"},{"key":"32_CR15","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0020-0190(00)00097-1","volume":"75","author":"R. Hassin","year":"2000","unstructured":"Rafael Hassin and Shlomi Rubinstein. Better approximations for max TSP. Information Processing Letters, 75:181\u2013186, 2000.","journal-title":"Information Processing Letters"},{"key":"32_CR16","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0166-218X(91)90011-K","volume":"30","author":"R. Hasssin","year":"1991","unstructured":"R. Hasssin and N. Meggido. Approximation algorithms for hitting objects with straight lines. Discrete Applied Mathematics, 30:29\u201342, 1991.","journal-title":"Discrete Applied Mathematics"},{"key":"32_CR17","unstructured":"Dorit Hochbaum, editor. Approximation Algorithms. PWS, 1997."},{"key":"32_CR18","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02294091","volume":"43","author":"L.J. Hubert","year":"1978","unstructured":"L.J. Hubert and F.B. Baker. Applications of combinatorial programming to data analysis: the traveling salesman and related problems. Pyschometrika, 43:81\u201391, 1978.","journal-title":"Pyschometrika"},{"key":"32_CR19","doi-asserted-by":"crossref","unstructured":"R. Kosaraju, J. Park, and C. Stein. Long tours and short superstrings. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 166\u2013177, 1994.","DOI":"10.1109\/SFCS.1994.365696"},{"key":"32_CR20","first-page":"55","volume":"26","author":"A. V. Kostochka","year":"1985","unstructured":"A. V. Kostochka and A. I. Serdyukov. Polynomial algorithms with the estimated 3\/4 and 5\/6 for the traveling salesman problem of the maximum (in russian). Upravlyaemye Sistemy, 26:55\u201359, 1985.","journal-title":"Upravlyaemye Sistemy"},{"key":"32_CR21","unstructured":"E.L. Lawler, J.K. Lenstra, A.H.G. Rinooy Kan, and D.B. Shmoys, editors. The Traveling Salesman Problem. John Wiley and Sons, 1985."},{"key":"32_CR22","volume-title":"Technical Report 92-AC-104","author":"D.T. Lee","year":"1992","unstructured":"D.T. Lee, C.D. Yang, and C.K. Wong. Problem transformation for finding rectilinear paths among obstacles in two-layer interconnection model. Technical Report 92-AC-104, Dept. of EECS, Northwestern University, 1992."},{"key":"32_CR23","doi-asserted-by":"crossref","unstructured":"D.T. Lee, C.D. Yang, and C.K. Wong. Rectilinear paths among rectilinear obstacles. Discrete Applied Mathematics, 70, 1996.","DOI":"10.1016\/0166-218X(96)80467-7"},{"key":"32_CR24","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1057\/jors.1975.151","volume":"26","author":"J.K. Lenstra","year":"1975","unstructured":"J.K. Lenstra and A.H.G. Rinnooy Kan. Some simple applications of the travelling salesman problem. Operations Research Quarterly, 26:717\u2013733, 1975.","journal-title":"Operations Research Quarterly"},{"key":"32_CR25","doi-asserted-by":"crossref","first-page":"993","DOI":"10.1287\/opre.20.5.993","volume":"20","author":"W.T. McCormick","year":"1972","unstructured":"W.T. McCormick, P.J. Schweitzer, and T.W. White. Problem decomposition and datareorganization by a clustering technique. Operations Research, 20:993\u20131009, 1972.","journal-title":"Operations Research"},{"key":"32_CR26","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1016\/0167-6377(82)90039-6","volume":"1","author":"N. Meggido","year":"1982","unstructured":"N. Meggido and A. Tamir. On the complexity of locating linear facilities in the plane. Operations Research Letters, 1:194\u2013197, 1982.","journal-title":"Operations Research Letters"},{"key":"32_CR27","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"J. S. B. Mitchell","year":"1999","unstructured":"Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM Journal on Computing, 28:1298\u20131309, 1999.","journal-title":"SIAM Journal on Computing"},{"key":"32_CR28","doi-asserted-by":"crossref","unstructured":"J.S.B. Mitchell, C. Piatko, and E.M. Arkin. Computing a shortest k-link path in a polygon. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 573\u2013582, 1992.","DOI":"10.1109\/SFCS.1992.267794"},{"key":"32_CR29","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1142\/S0218195992000056","volume":"2","author":"C.D. Yang","year":"1992","unstructured":"C.D. Yang, D.T. Lee, and C.K. Wong. On bends and lengths of rectilinear paths: a graph-theoretic approach. Internat. J. Comp. Geom. Appl., 2:61\u201374, 1992.","journal-title":"Internat. J. Comp. Geom. Appl."},{"key":"32_CR30","volume-title":"Technical Report 92-AC-122","author":"C.D. Yang","year":"1992","unstructured":"C.D. Yang, D.T. Lee, and C.K. Wong. On minimum-bend shortest recilinear path among weighted rectangles. Technical Report 92-AC-122, Dept. of EECS, North-western University, 1992."},{"key":"32_CR31","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1137\/S0097539792229672","volume":"24","author":"C.D. Yang","year":"1992","unstructured":"C.D. Yang, D.T. Lee, and C.K. Wong. Rectilinear path problems among rectilinear obstacles revisited. SIAM Journal on Computing, 24:457\u2013472, 1992.","journal-title":"SIAM Journal on Computing"},{"key":"32_CR32","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1109\/12.280808","volume":"43","author":"C.D. Yang","year":"1994","unstructured":"C.D. Yang, D.T. Lee, and C.K. Wong. On bends and distance paths among obstacles in two-layer interconnection model. IEEE Transactions on Computers, 43:711\u2013724, 1994.","journal-title":"IEEE Transactions on Computers"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","deposited":{"date-parts":[[2019,5,25]],"date-time":"2019-05-25T18:29:21Z","timestamp":1558808961000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45535-3_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540422259"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/3-540-45535-3_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}