{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:30:36Z","timestamp":1758274236365,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2010,6,1]],"date-time":"2010-06-01T00:00:00Z","timestamp":1275350400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2010,6]]},"abstract":"<jats:p>\n            Given a rectangular boundary partitioned into rectangles, the Minimum-Length Corridor (MLC-R) problem consists of finding a corridor of least total length. A corridor is a set of connected line segments, each of which must lie along the line segments that form the rectangular boundary and\/or the boundary of the rectangles, and must include at least one point from the boundary of every rectangle and from the rectangular boundary. The MLC-R problem is known to be NP-hard. We present the first polynomial-time constant ratio approximation algorithm for the MLC-R and MLC\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            problems. The MLC\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            problem is a generalization of the MLC-R problem where the rectangles are rectilinear\n            <jats:italic>c<\/jats:italic>\n            -gons, for\n            <jats:italic>c<\/jats:italic>\n            \u2264\n            <jats:italic>k<\/jats:italic>\n            and\n            <jats:italic>k<\/jats:italic>\n            is a constant. We also present the first polynomial-time constant ratio approximation algorithm for the Group Traveling Salesperson Problem (GTSP) for a rectangular boundary partitioned into rectilinear\n            <jats:italic>c<\/jats:italic>\n            -gons as in the MLC\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            problem. Our algorithms are based on the restriction and relaxation approximation techniques.\n          <\/jats:p>","DOI":"10.1145\/1798596.1798609","type":"journal-article","created":{"date-parts":[[2010,6,29]],"date-time":"2010-06-29T13:02:22Z","timestamp":1277816542000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximating corridors and tours via restriction and relaxation techniques"],"prefix":"10.1145","volume":"6","author":[{"given":"Arturo","family":"Gonzalez-Gutierrez","sequence":"first","affiliation":[{"name":"University of California, Santa Barbara, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Teofilo F.","family":"Gonzalez","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,7,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/267665.267697"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11970125_6"},{"volume-title":"Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG01)","year":"2001","author":"Demaine E. D.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","unstructured":"Eppstein D. 2001. Some open problems in graph theory and computational geometry. PDF file (3.89 MB) World Wide Web. http:\/\/www.ics.uci.edu\/~eppstein\/200-f01.pdf.  Eppstein D. 2001. Some open problems in graph theory and computational geometry. PDF file (3.89 MB) World Wide Web. http:\/\/www.ics.uci.edu\/~eppstein\/200-f01.pdf."},{"volume-title":"TR 2007-03","author":"Gonzalez-Gutierrez A.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.10.002"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0037(200101)37:1<8::AID-NET2>3.0.CO;2-R"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/124223.124233"},{"key":"e_1_2_1_9_1","unstructured":"Jin L. Y. and Chong O. W. 2003. The minimum touching tree problem. PDF file (189 KB) World Wide Web. http:\/\/www.yewjin.com\/research\/MinimumTouchingTrees.pdf.  Jin L. Y. and Chong O. W. 2003. The minimum touching tree problem. PDF file (189 KB) World Wide Web. http:\/\/www.yewjin.com\/research\/MinimumTouchingTrees.pdf."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Karp R. M. 1972. Reducibility among combinatorial problems. Complex. Comput. Comput. 85--103.  Karp R. M. 1972. Reducibility among combinatorial problems. Complex. Comput. Comput. 85--103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535331_16"},{"volume-title":"Handbook of Computational Geometry","author":"Mitchell J. S. B.","key":"e_1_2_1_12_1"},{"volume-title":"Proceedings of the 15th International Workshop on Graph-Theoretic Concepts in Computer Science (WG89)","author":"Reich G.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0200-3"},{"key":"e_1_2_1_15_1","unstructured":"Slavik P. 1997. The errand scheduling problem. Tech. rep. 97-02 Department of Computer Science and Engineering University of New York at Buffalo. http:\/\/www.cse.buffalo.edu\/tech-reports\/.  Slavik P. 1997. The errand scheduling problem. Tech. rep. 97-02 Department of Computer Science and Engineering University of New York at Buffalo. http:\/\/www.cse.buffalo.edu\/tech-reports\/."},{"key":"e_1_2_1_16_1","unstructured":"Slavik P. 1998. Approximation algorithms for set cover and related problems. Ph. D. thesis 98-06 Department of Computer Science and Engineering University of New York at Buffalo. http:\/\/www.cse.buffalo.edu\/tech-reports\/.   Slavik P. 1998. Approximation algorithms for set cover and related problems. Ph. D. thesis 98-06 Department of Computer Science and Engineering University of New York at Buffalo. http:\/\/www.cse.buffalo.edu\/tech-reports\/."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1798596.1798609","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1798596.1798609","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:43:36Z","timestamp":1750286616000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1798596.1798609"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,6]]}},"alternative-id":["10.1145\/1798596.1798609"],"URL":"https:\/\/doi.org\/10.1145\/1798596.1798609","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2010,6]]},"assertion":[{"value":"2007-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-07-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}