乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:17:08Z","timestamp":1740143828177,"version":"3.37.3"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,4,25]],"date-time":"2016-04-25T00:00:00Z","timestamp":1461542400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["DMS-1001667, CCF-0830734 and CCF-1423615"]},{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","award":["RGPIN 35586"],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,6,15]]},"abstract":"\n We revisit the traveling salesman problem with neighborhoods (TSPN) and propose several new approximation algorithms. These constitute either first approximations (for hyperplanes, lines, and balls in R\n \n d<\/jats:sup>\n <\/jats:italic>\n , for\n d<\/jats:italic>\n \u2a7e 3) or improvements over previous approximations achievable in comparable times (for unit disks in the plane).\n <\/jats:p>\n \n (I) Given a set of\n n<\/jats:italic>\n hyperplanes in R\n \n d<\/jats:sup>\n <\/jats:italic>\n , a traveling salesman problem (TSP) tour whose length is at most\n O<\/jats:italic>\n (1) times the optimal can be computed in\n O<\/jats:italic>\n (\n n<\/jats:italic>\n ) time when\n d<\/jats:italic>\n is constant.\n <\/jats:p>\n \n (II) Given a set of\n n<\/jats:italic>\n lines in R\n \n d<\/jats:sup>\n <\/jats:italic>\n , a TSP tour whose length is at most\n O<\/jats:italic>\n (log\n 3<\/jats:sup>\n n<\/jats:italic>\n ) times the optimal can be computed in polynomial time for all\n d<\/jats:italic>\n .\n <\/jats:p>\n \n (III) Given a set of\n n<\/jats:italic>\n unit balls in R\n \n d<\/jats:sup>\n <\/jats:italic>\n , a TSP tour whose length is at most\n O<\/jats:italic>\n (1) times the optimal can be computed in polynomial time when\n d<\/jats:italic>\n is constant.\n <\/jats:p>","DOI":"10.1145\/2850418","type":"journal-article","created":{"date-parts":[[2016,4,25]],"date-time":"2016-04-25T19:51:13Z","timestamp":1461613873000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["The Traveling Salesman Problem for Lines, Balls, and Planes"],"prefix":"10.1145","volume":"12","author":[{"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[{"name":"University of Wisconsin--Milwaukee, WI, USA"}]},{"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[{"name":"California State University, Northridge, CA, USA"}]}],"member":"320","published-online":{"date-parts":[[2016,4,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90008-6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214038"},{"key":"e_1_2_1_4_1","unstructured":"M. Bern and D. Eppstein. 1997. Approximation Algorithms for Geometric Problems. PWS Publishing Company Boston MA 296--345. M. Bern and D. Eppstein. 1997. Approximation Algorithms for Geometric Problems. PWS Publishing Company Boston MA 296--345."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90039-2"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.05.001"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009467"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116672.3117140"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884489"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0060"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1115481.1712332"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780612"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/050636589"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1142\/S1793830912500449"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9516-3"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00047-6"},{"key":"e_1_2_1_18_1","unstructured":"A. Dumitrescu and C. D. T\u00f3th. 2015a. Constant-factor approximation for TSP with disks. arXiv:1506.07903v2. A. Dumitrescu and C. D. T\u00f3th. 2015a. Constant-factor approximation for TSP with disks. arXiv:1506.07903v2."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13366-014-0219-1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"M. Dyer N. Megiddo and E. Welzl. 2004. Linear programming. In Handbook of Discrete and Computational Geometry (2nd ed.) J. E. Goodman and J. O\u2019Rourke (Eds.). CRC Press Boca Raton FL. M. Dyer N. Megiddo and E. Welzl. 2004. Linear programming. In Handbook of Discrete and Computational Geometry (2nd ed.) J. E. Goodman and J. O\u2019Rourke (Eds.). CRC Press Boca Raton FL.","DOI":"10.1201\/9781420035315.pt6"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_90"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11940128_23"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195909002897"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300000784"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321942"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/800113.803626"},{"key":"e_1_2_1_28_1","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company New York NY. M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company New York NY."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1096"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/642160.642167"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780628"},{"volume-title":"Abstracts of the 27th European Workshop on Computational Geometry. 51--54","author":"H\u00e4me L.","key":"e_1_2_1_32_1","unstructured":"L. H\u00e4me , E. Hyyti\u00e4 , and H. Hakula . 2011. The traveling salesman problem with differential neighborhoods . In Abstracts of the 27th European Workshop on Computational Geometry. 51--54 . L. H\u00e4me, E. Hyyti\u00e4, and H. Hakula. 2011. The traveling salesman problem with differential neighborhoods. In Abstracts of the 27th European Workshop on Computational Geometry. 51--54."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00259-9"},{"key":"e_1_2_1_34_1","volume-title":"Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science","volume":"181","author":"Levcopoulos C.","unstructured":"C. Levcopoulos and A. Lingas . 1984. Bounds on the length of convex partitions of polygons . In Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science , Vol. 181 . Springer, 279--295. C. Levcopoulos and A. Lingas. 1984. Bounds on the length of convex partitions of polygons. In Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science, Vol. 181. Springer, 279--295."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/220279.220318"},{"key":"e_1_2_1_36_1","first-page":"496","article-title":"A subexponential bound for linear programming","volume":"16","author":"Matou\u0161ek J.","year":"1996","unstructured":"J. Matou\u0161ek , M. Sharir , and E. Welzl . 1996 . A subexponential bound for linear programming . Algorithmica 16 , 496 -- 516 . J. Matou\u0161ek, M. Sharir, and E. Welzl. 1996. A subexponential bound for linear programming. Algorithmica 16, 496--516.","journal-title":"Algorithmica"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"E. W. Mayr H. J. Pr\u00f6mel and A. Steger (Eds.). 1998. Lectures on Proof Verification and Approximation Algorithms. Springer Heidelberg Germany. E. W. Mayr H. J. Pr\u00f6mel and A. Steger (Eds.). 1998. Lectures on Proof Verification and Approximation Algorithms. Springer Heidelberg Germany.","DOI":"10.1007\/BFb0053010"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422.322418"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"volume-title":"Handbook of Computational Geometry, J.-R","author":"Mitchell J. S. B.","key":"e_1_2_1_40_1","unstructured":"J. S. B. Mitchell . 2000. Geometric shortest paths and network optimization . In Handbook of Computational Geometry, J.-R . Sack and J. Urrutia (Eds.). Elsevier , Amsterdam , 633--701. J. S. B. Mitchell. 2000. Geometric shortest paths and network optimization. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia (Eds.). Elsevier, Amsterdam, 633--701."},{"key":"e_1_2_1_41_1","volume-title":"Handbook of Discrete and Computational Geometry","author":"Mitchell J. S. B.","unstructured":"J. S. B. Mitchell . 2004. Shortest paths and networks . In Handbook of Discrete and Computational Geometry ( 2 nd ed.), J. E. Goodman and J. O\u2019Rourke (Eds.). CRC Press , Boca Raton, FL, 607--641. J. S. B. Mitchell. 2004. Shortest paths and networks. In Handbook of Discrete and Computational Geometry (2nd ed.), J. E. Goodman and J. O\u2019Rourke (Eds.). CRC Press, Boca Raton, FL, 607--641.","edition":"2"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the Symposium on Discrete Algorithms (SODA\u201907)","author":"Mitchell J. S. B.","year":"2007","unstructured":"J. S. B. Mitchell . 2007 . A PTAS for TSP with neighborhoods among fat regions in the plane . In Proceedings of the Symposium on Discrete Algorithms (SODA\u201907) . ACM, New York, NY, 11--18. J. S. B. Mitchell. 2007. A PTAS for TSP with neighborhoods among fat regions in the plane. In Proceedings of the Symposium on Discrete Algorithms (SODA\u201907). ACM, New York, NY, 11--18."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810959.1810992"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90012-3"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276868"},{"key":"e_1_2_1_47_1","volume-title":"Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science","volume":"411","author":"Reich G.","unstructured":"G. Reich and P. Widmayer . 1990. Beyond Steiner\u2019s problem: A VLSI oriented generalization . In Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science , Vol. 411 . Springer, 196--210. G. Reich and P. Widmayer. 1990. Beyond Steiner\u2019s problem: A VLSI oriented generalization. In Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science, Vol. 411. Springer, 196--210."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0200-3"},{"key":"e_1_2_1_50_1","unstructured":"S. Spirkl. 2014. The guillotine subdivision approach for TSP with neighborhoods revisited. arXiv:1312.0378 {cs.CG} http:\/\/arxiv.org\/abs\/1312.0378 S. Spirkl. 2014. The guillotine subdivision approach for TSP with neighborhoods revisited. arXiv:1312.0378 {cs.CG} http:\/\/arxiv.org\/abs\/1312.0378"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00146-0"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195999000212"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796458"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2850418","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T09:07:29Z","timestamp":1672477649000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2850418"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,25]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,6,15]]}},"alternative-id":["10.1145\/2850418"],"URL":"https:\/\/doi.org\/10.1145\/2850418","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2016,4,25]]},"assertion":[{"value":"2014-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-04-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}