{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:20:44Z","timestamp":1750306844830,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":15,"publisher":"ACM","license":[{"start":{"date-parts":[[2014,6,8]],"date-time":"2014-06-08T00:00:00Z","timestamp":1402185600000},"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":[],"published-print":{"date-parts":[[2014,6,8]]},"DOI":"10.1145\/2582112.2582136","type":"proceedings-article","created":{"date-parts":[[2014,5,2]],"date-time":"2014-05-02T14:01:31Z","timestamp":1399039291000},"page":"130-135","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["A near-optimal approximation algorithm for Asymmetric TSP on embedded graphs"],"prefix":"10.1145","author":[{"given":"Jeff","family":"Erickson","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Illinois, Urbana-Champaign"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anastasios","family":"Sidiropoulos","sequence":"additional","affiliation":[{"name":"Department of Computer Science & Engineering and Department of Mathematics, The Ohio State University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,6,8]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Shayan Oveis Gharan, and Amin Saberi. An O(log n\/loglog n)-approximation algorithm for the asymmetric traveling salesman problem. SODA, 379--389","author":"Asadpour Arash","year":"2010","unstructured":"Arash Asadpour , Michel X. Goemans , Aleksander Madry , Shayan Oveis Gharan, and Amin Saberi. An O(log n\/loglog n)-approximation algorithm for the asymmetric traveling salesman problem. SODA, 379--389 , 2010 . Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, and Amin Saberi. An O(log n\/loglog n)-approximation algorithm for the asymmetric traveling salesman problem. SODA, 379--389, 2010."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321111"},{"key":"e_1_3_2_1_3_1","volume-title":"Proc., 14th Ann. ACM-SIAM Symp. Discrete Algorithms, 638--645","author":"Bl\u00e4ser Markus","year":"2003","unstructured":"Markus Bl\u00e4ser . A new approximation algorithm for the asymmetric tsp with triangle inequality . Proc., 14th Ann. ACM-SIAM Symp. Discrete Algorithms, 638--645 , 2003 . Markus Bl\u00e4ser. A new approximation algorithm for the asymmetric tsp with triangle inequality. Proc., 14th Ann. ACM-SIAM Symp. Discrete Algorithms, 638--645, 2003."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.26"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392203"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74208-1_8"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120103"},{"issue":"1","key":"e_1_3_2_1_8_1","first-page":"196","article-title":"A dynamic programming approach to sequencing problems","volume":"10","author":"Held Michael","year":"1962","unstructured":"Michael Held and Richard Karp . A dynamic programming approach to sequencing problems . J. SIAM 10 ( 1 ): 196 -- 210 , 1962 . Michael Held and Richard Karp. A dynamic programming approach to sequencing problems. J. SIAM 10(1):196--210, 1962.","journal-title":"J. SIAM"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.18.6.1138"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1090\/psapm\/010\/0114759"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082041"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.53"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"Mohar Bojan","year":"2001","unstructured":"Bojan Mohar and Carsten Thomassen . Graphs on Surfaces . Johns Hopkins Univ. Press , 2001 . Bojan Mohar and Carsten Thomassen. Graphs on Surfaces. Johns Hopkins Univ. Press, 2001."},{"key":"e_1_3_2_1_14_1","volume-title":"The asymmetric traveling salesman problem on graphs with bounded genus. SODA, 967--975","author":"Gharan Shayan Oveis","year":"2011","unstructured":"Shayan Oveis Gharan and Amin Saberi . The asymmetric traveling salesman problem on graphs with bounded genus. SODA, 967--975 , 2011 . SIAM. Shayan Oveis Gharan and Amin Saberi. The asymmetric traveling salesman problem on graphs with bounded genus. SODA, 967--975, 2011. SIAM."},{"key":"e_1_3_2_1_15_1","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics 24","author":"Schrijver Alexander","year":"2003","unstructured":"Alexander Schrijver . Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics 24 . Springer , 2003 . Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics 24. Springer, 2003."}],"event":{"name":"SOCG'14: Annual Symposium on Computational Geometry","sponsor":["SIGGRAPH ACM Special Interest Group on Computer Graphics and Interactive Techniques","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Kyoto Japan","acronym":"SOCG'14"},"container-title":["Proceedings of the thirtieth annual symposium on Computational geometry"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2582112.2582136","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2582112.2582136","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:09Z","timestamp":1750234209000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2582112.2582136"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,8]]},"references-count":15,"alternative-id":["10.1145\/2582112.2582136","10.1145\/2582112"],"URL":"https:\/\/doi.org\/10.1145\/2582112.2582136","relation":{},"subject":[],"published":{"date-parts":[[2014,6,8]]},"assertion":[{"value":"2014-06-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}