乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T18:40:04Z","timestamp":1731004804156,"version":"3.28.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,1,8]],"date-time":"2024-01-08T00:00:00Z","timestamp":1704672000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,8]],"date-time":"2024-01-08T00:00:00Z","timestamp":1704672000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100019926","name":"Nederlandse Organisatie voor Toegepast Natuurwetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["NETWORKS-024.002.003"],"id":[{"id":"10.13039\/501100019926","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2024,6]]},"DOI":"10.1007\/s00454-023-00609-7","type":"journal-article","created":{"date-parts":[[2024,1,8]],"date-time":"2024-01-08T22:01:37Z","timestamp":1704751297000},"page":"1456-1506","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Euclidean TSP in Narrow Strips"],"prefix":"10.1007","volume":"71","author":[{"ORCID":"http:\/\/orcid.org\/0000-0003-4141-1191","authenticated-orcid":false,"given":"Henk","family":"Alkema","sequence":"first","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0001-5770-3784","authenticated-orcid":false,"given":"Mark","family":"de Berg","sequence":"additional","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0003-1331-9697","authenticated-orcid":false,"given":"Remco","family":"van der Hofstad","sequence":"additional","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0002-6856-2902","authenticated-orcid":false,"given":"S\u00e1ndor","family":"Kisfaludi-Bak","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,1,8]]},"reference":[{"key":"609_CR1","unstructured":"Alkema, H., de\u00a0Berg, M.: Rectilinear Steiner trees in narrow strips. In: Proceedings of 37th International Symposium on Computational Geometry (SoCG), pp. 9:1\u20139:16 (2021)"},{"issue":"5","key":"609_CR2","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753\u2013782 (1998)","journal-title":"J. ACM"},{"key":"609_CR3","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86\u2013111 (2015)","journal-title":"Inf. Comput."},{"key":"609_CR4","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report. Graduate School of Industrial Administration, Carnegie Mellon University (1976)"},{"key":"609_CR5","volume-title":"Introduction to Algorithms","author":"T Cormen","year":"2009","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 3rd edn. MIT, Cambridge (2009)","edition":"3"},{"key":"609_CR6","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1002\/net.3230100302","volume":"10","author":"M Cutler","year":"1980","unstructured":"Cutler, M.: Efficient special case algorithms for the $$n$$-line planar traveling salesman problem. Networks 10, 183\u2013195 (1980)","journal-title":"Networks"},{"issue":"3","key":"609_CR7","doi-asserted-by":"publisher","first-page":"12:1","DOI":"10.1145\/3148227","volume":"65","author":"M Cygan","year":"2018","unstructured":"Cygan, M., Kratsch, S., Nederlof, J.: Fast Hamiltonicity checking via bases of perfect matchings. J. ACM 65(3), 12:1-12:46 (2018)","journal-title":"J. ACM"},{"key":"609_CR8","volume-title":"An Introduction to the Theory of Point Processes: Volume II: General Theory and Structure. Probability and Its Applications","author":"D Daley","year":"2007","unstructured":"Daley, D., Vere-Jones, D.: An Introduction to the Theory of Point Processes: Volume II: General Theory and Structure. Probability and Its Applications. Springer, New York (2007)"},{"key":"609_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M de Berg","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer, Berlin (2008)"},{"key":"609_CR10","unstructured":"de\u00a0Berg, M., Buchin, K., Jansen, B., Woeginger, G.: Fine-grained complexity analysis of two classic TSP variants. In: Proceedings of 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 5:1\u20135:14 (2016)"},{"issue":"1","key":"609_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3414845","volume":"17","author":"M de Berg","year":"2016","unstructured":"de Berg, M., Buchin, K., Jansen, B.M.P., Woeginger, G.J.: Fine-grained complexity analysis of two classic TSP variants. ACM Trans. Algorithms 17(1), 1\u201329 (2016)","journal-title":"ACM Trans. Algorithms"},{"key":"609_CR12","doi-asserted-by":"crossref","unstructured":"de\u00a0Berg, M., Bodlaender, H., Kisfaludi-Bak, S., Kolay, S.: An ETH-tight exact algorithm for Euclidean TSP. In: Proceedings of 59th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 450\u2013461 (2018)","DOI":"10.1109\/FOCS.2018.00050"},{"issue":"3","key":"609_CR13","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0020-0190(96)00125-1","volume":"59","author":"V Deineko","year":"1996","unstructured":"Deineko, V., Woeginger, G.: The convex-hull-and-$k$-lines traveling salesman problem. Inf. Proc. Lett. 59(3), 295\u2013301 (1996)","journal-title":"Inf. Proc. Lett."},{"key":"609_CR14","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0020-0190(94)00071-9","volume":"51","author":"V Deineko","year":"1994","unstructured":"Deineko, V., van Dal, R., Rote, G.: The convex-hull-and-line traveling salesman problem: a solvable case. Inf. Proc. Lett. 51, 141\u2013148 (1994)","journal-title":"Inf. Proc. Lett."},{"issue":"1","key":"609_CR15","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/j.orl.2005.01.002","volume":"34","author":"V Deineko","year":"2006","unstructured":"Deineko, V., Hoffmann, M., Okamoto, Y., Woeginger, G.: The traveling salesman problem with few inner points. Oper. Res. Lett. 34(1), 106\u2013110 (2006)","journal-title":"Oper. Res. Lett."},{"key":"609_CR16","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0304-3975(89)90133-3","volume":"66","author":"H Edelsbrunner","year":"1989","unstructured":"Edelsbrunner, H., Rote, G., Welzl, E.: Testing the necklace condition for shortest tours and optimal factors in the plane. Theor. Comput. Sci. 66, 157\u2013180 (1989)","journal-title":"Theor. Comput. Sci."},{"key":"609_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3381420","volume":"16","author":"F Fomin","year":"2020","unstructured":"Fomin, F., Lokshtanov, D., Kolay, S., Panolan, F., Saurabh, S.: Subexponential algorithms for rectilinear Steiner tree and arborescence problems. ACM Trans. Algorithms 16, 1\u201337 (2020). https:\/\/doi.org\/10.1145\/3381420","journal-title":"ACM Trans. Algorithms"},{"key":"609_CR18","doi-asserted-by":"crossref","unstructured":"Garey, M., Graham, R., Johnson, D.: Some NP-complete geometric problems. In: Proceedings of the 8th Annual ACM Symposium on Theory of Computing (STOC), pp. 10\u201322 (1976)","DOI":"10.1145\/800113.803626"},{"issue":"4","key":"609_CR19","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1007\/BF01228511","volume":"9","author":"R Hwang","year":"1993","unstructured":"Hwang, R., Chang, R., Lee, R.: The searching over separators strategy to solve some NP-hard problems in subexponential time. Algorithmica 9(4), 398\u2013423 (1993)","journal-title":"Algorithmica"},{"issue":"2","key":"609_CR20","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"609_CR21","unstructured":"Kann, V.: On the approximability of NP-complete optimization problems. Ph.D. thesis, Royal Institute of Technology, Stockholm (1992)"},{"issue":"4","key":"609_CR22","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"J Mitchell","year":"1999","unstructured":"Mitchell, J.: 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)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"609_CR23","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"C Papadimitriou","year":"1977","unstructured":"Papadimitriou, C.: The Euclidean traveling salesman problem is NP-complete. Theor. Comput. Sci. 4(3), 237\u2013244 (1977)","journal-title":"Theor. Comput. Sci."},{"key":"609_CR24","doi-asserted-by":"crossref","unstructured":"Rao, S., Smith, W.D.: Approximating geometrical graphs via \u2018spanners\u2019 and \u2018banyans\u2019. In: Proceedings of 30th ACM Symposium on Theory of Computing (STOC), pp. 540\u2013550 (1998)","DOI":"10.1145\/276698.276868"},{"key":"609_CR25","unstructured":"Reinhold, A.: Some results on minimal covertex polygons. Manuscript, City College of New York (1965)"},{"issue":"2","key":"609_CR26","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1214\/aoms\/1177732430","volume":"8","author":"J Riordan","year":"1937","unstructured":"Riordan, J.: Moment recurrence relations for binomial, Poisson and hypergeometric frequency distributions. Ann. Math. Stat. 8(2), 103\u2013111 (1937). https:\/\/doi.org\/10.1214\/aoms\/1177732430","journal-title":"Ann. Math. Stat."},{"key":"609_CR27","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1002\/net.3230220106","volume":"22","author":"G Rote","year":"1992","unstructured":"Rote, G.: The $$n$$-line traveling salesman problem. Networks 22, 91\u2013108 (1992)","journal-title":"Networks"},{"key":"609_CR28","unstructured":"Sanders, D.: On extreme circuits. Ph.D. thesis, City University of New York (1968)"},{"key":"609_CR29","doi-asserted-by":"crossref","unstructured":"Smith, W., Wormald, N.: Geometric separator theorems and applications. In: Proceedings 39th Annual Symposium on Foundations of Computer Science (FOCS), pp. 232\u2013243 (1998)","DOI":"10.1109\/SFCS.1998.743449"},{"key":"609_CR30","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1236-2","volume-title":"Coupling, Stationarity and Regeneration","author":"H Thorisson","year":"2000","unstructured":"Thorisson, H.: Coupling, Stationarity and Regeneration. Springer, New York (2000)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00609-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00609-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00609-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T18:16:17Z","timestamp":1731003377000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00609-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,8]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["609"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00609-7","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2024,1,8]]},"assertion":[{"value":"30 March 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 June 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 September 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}