{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T18:40:03Z","timestamp":1738348803428,"version":"3.35.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540853626"},{"type":"electronic","value":"9783540853633"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85363-3_17","type":"book-chapter","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T19:29:28Z","timestamp":1219865368000},"page":"207-218","source":"Crossref","is-referenced-by-count":0,"title":["A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem"],"prefix":"10.1007","author":[{"given":"Th\u00e0nh","family":"Nguyen","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"Bansal, N., Khandekar, R., Nagarajan, V.: Additive Guarantees for Degree Bounded Directed Network Design. In: STOC 2008 (2008)","DOI":"10.1145\/1374376.1374486"},{"key":"17_CR2","unstructured":"Bl\u00e4ser, M.: A new Approximation Algorithm for the Asymmetric TSP with Triangle Inequality. In: SODA 2002, pp. 638\u2013645 (2002)"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Charikar, M., Goemans, M.X., Karloff, H.J.: On the Integrality Ratio for Asymmetric TSP. In: FOCS 2004, pp. 101\u2013107 (2004)","DOI":"10.1109\/FOCS.2004.45"},{"issue":"3","key":"17_CR4","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/s10107-004-0506-y","volume":"100","author":"R. Carr","year":"2004","unstructured":"Carr, R., Vempala, S.: On the Held-Karp relaxation for the asymmetric and symmetric TSPs. Mathematical Programming\u00a0100(3), 569\u2013587 (2004)","journal-title":"Mathematical Programming"},{"key":"17_CR5","unstructured":"Frank, A.: Personal communication"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"Frieze, A., Galbiati, G., Maffioli, M.: On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks\u00a012 (1982)","DOI":"10.1002\/net.3230120103"},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"Goemans, M.X.: Minimum Bounded Degree Spanning Trees. In: FOCS 2006, pp. 273\u2013282 (2006)","DOI":"10.1109\/FOCS.2006.48"},{"volume-title":"Traveling Salesman Problem and Its Variations","year":"2002","key":"17_CR8","unstructured":"Gutin, G., Punnen, A.P. (eds.): Traveling Salesman Problem and Its Variations. Springer, Berlin (2002)"},{"key":"17_CR9","doi-asserted-by":"publisher","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M. Held","year":"1970","unstructured":"Held, M., Karp, R.M.: The traveling salesman problem and minimum spanning trees. Operation Research\u00a018, 1138\u20131162 (1970)","journal-title":"Operation Research"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"Hoffman, A.J.: Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. In: Proc. Symp. in Applied Mathematics, Amer. Math. Soc., pp. 113\u2013127 (1960)","DOI":"10.1090\/psapm\/010\/0114759"},{"key":"17_CR11","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s004930170004","volume":"21","author":"K. Jain","year":"2001","unstructured":"Jain, K.: A factor 2 approximation for the generalized Steiner network problem. Combinatorica\u00a021, 39\u201360 (2001)","journal-title":"Combinatorica"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Lewenstein, M., Shafir, N., Sviridenko, M.: Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multidigraphs. In: Proc. of IEEE FOCS, pp. 56\u201367 (2003)","DOI":"10.1109\/SFCS.2003.1238181"},{"key":"17_CR13","volume-title":"Combinatorial Optimization - Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization - Polyhedra and Efficiency. Springer, Berlin (2003)"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Lau, L.C., Naor, J., Salavatipour, M.R., Singh, M.: Survivable network design with degree or order constraints. In: STOC 2007, pp. 651\u2013660 (2007)","DOI":"10.1145\/1250790.1250886"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"Lau, L.C., Singh, M.: Approximating minimum bounded degree spanning trees to within one of optimal. In: STOC 2007, pp. 661\u2013670 (2007)","DOI":"10.1145\/1250790.1250887"},{"volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","year":"1985","key":"17_CR16","unstructured":"Lawler, E., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D. (eds.): The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons Ltd., Chichester (1985)"},{"key":"17_CR17","unstructured":"Vempala, S., Yannakakis, M.: A Convex Relaxation for the Asymmetric TSP. In: SODA 1999, pp. 975\u2013976 (1999)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85363-3_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T18:12:28Z","timestamp":1738347148000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85363-3_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540853626","9783540853633"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85363-3_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}