{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:14:35Z","timestamp":1781345675024,"version":"3.54.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2014,10,1]],"date-time":"2014-10-01T00:00:00Z","timestamp":1412121600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2014,10]]},"DOI":"10.1007\/s00493-014-2960-3","type":"journal-article","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T21:17:23Z","timestamp":1415999843000},"page":"597-629","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":101,"title":["Shorter tours by nicer ears: 7\/5-Approximation for the graph-TSP, 3\/2 for the path version, and 4\/3 for two-edge-connected subgraphs"],"prefix":"10.1007","volume":"34","author":[{"given":"Andr\u00e1s","family":"Seb\u0151","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jens","family":"Vygen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2014,11,11]]},"reference":[{"key":"2960_CR1","volume-title":"On the integrality gap of the 2-edge connected subgraph problem","author":"A. Alexander","year":"2006","unstructured":"A. Alexander, S. Boyd, and P. Elliott-Magwood: On the integrality gap of the 2-edge connected subgraph problem, Technical Report TR-2006-04, SITE, University of Ottawa, 2006."},{"key":"2960_CR2","first-page":"875","volume-title":"Proceedings of the 44th Annual ACM Symposium on Theory of Computing","author":"H.-C. An","year":"2012","unstructured":"H.-C. An, R. Kleinberg, and D. B. Shmoys: Improving Christofides\u2019 algorithm for the s-t path TSP, Proceedings of the 44th Annual ACM Symposium on Theory of Computing (2012), 875\u2013886"},{"key":"2960_CR3","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0012-365X(87)90097-5","volume":"66","author":"F. Barahona","year":"1987","unstructured":"F. Barahona and M. Conforti: A construction for binary matroids, Discrete Mathematics 66 (1987), 213\u2013218.","journal-title":"Discrete Mathematics"},{"key":"2960_CR4","first-page":"65","volume-title":"Integer Programming and Combinatorial Optimization","author":"S. Boyd","year":"2011","unstructured":"S. Boyd, R. Sitters, S. van der Ster and L. Stougie: TSP on cubic and subcubic graphs, in: Integer Programming and Combinatorial Optimization; Proceedings of the 15th IPCO Conference; LNCS 6655 (O. G\u00fcnl\u00fck, G.J. Woeginger, eds.), Springer, Berlin 2011, 65\u201377."},{"key":"2960_CR5","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/3-540-69346-7_9","volume-title":"Integer Programming and Combinatorial Optimization","author":"R. Carr","year":"1998","unstructured":"R. Carr and R. Ravi: A new bound for the 2-edge connected subgraph problem, in: Integer Programming and Combinatorial Optimization; Proceedings of the 6th IPCO Conference; LNCS 1412 (R.E. Bixby, E.A. Boyd, R.Z. R\u00edos-Mercado, eds.), Springer, Berlin 1998, 112\u2013125."},{"key":"2960_CR6","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1137\/S0895480199362071","volume":"14","author":"J. Cheriyan","year":"2001","unstructured":"J. Cheriyan, A. Seb\u0151 and Z. Szigeti: Improving on the 1.5-approximation of a smallest 2-edge connected spanning subgraph, SIAM Journal on Discrete Mathematics 14 (2001), 170\u2013180.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"2960_CR7","series-title":"Technical Report","volume-title":"Worst-case analysis of a new heuristic for the traveling salesman problem","author":"N. Christofides","year":"1976","unstructured":"N. Christofides: Worst-case analysis of a new heuristic for the traveling salesman problem, Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh 1976."},{"key":"2960_CR8","volume-title":"In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation","author":"W. J. Cook","year":"2012","unstructured":"W. J. Cook: In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, Princeton University Press 2012."},{"key":"2960_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01582008","volume":"33","author":"G. Cornu\u00e9jols","year":"1985","unstructured":"G. Cornu\u00e9jols, J. Fonlupt and D. Naddef: The traveling salesman problem on a graph and some related integer polyhedra, Mathematical Programming 33 (1985), 1\u201327.","journal-title":"Mathematical Programming"},{"key":"2960_CR10","first-page":"3","volume":"13","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds: The Chinese postman\u2019s problem, Bulletin of the Operations Research Society of America 13 (1965), 3\u20133.","journal-title":"Bulletin of the Operations Research Society of America"},{"key":"2960_CR11","first-page":"69","volume-title":"Combinatorial Structures and Their Applications","author":"J. Edmonds","year":"1970","unstructured":"J. Edmonds: Submodular functions, matroids and certain polyhedra, in: Combinatorial Structures and Their Applications; Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications 1969 (R. Guy, H. Hanani, N. Sauer, J. Sch\u00f6nheim, eds.), Gordon and Breach, New York 1970, 69\u201387."},{"key":"2960_CR12","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J. Edmonds","year":"1973","unstructured":"J. Edmonds and E. L. Johnson: Matching, Euler tours and the Chinese postman, Mathematical Programming 5 (1973), 88\u2013124.","journal-title":"Mathematical Programming"},{"key":"2960_CR13","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF01202790","volume":"13","author":"A. Frank","year":"1993","unstructured":"A. Frank: Conservative weightings and ear-decompositions of graphs, Combinatorica 13 (1993), 65\u201381.","journal-title":"Combinatorica"},{"key":"2960_CR14","volume-title":"Connections in Combinatorial Optimization","author":"A. Frank","year":"2011","unstructured":"A. Frank: Connections in Combinatorial Optimization, Oxford University Press 2011."},{"key":"2960_CR15","volume-title":"Implementation of algorithms for maximum matching on nonbipartite graphs","author":"H. N. Gabow","year":"1973","unstructured":"H. N. Gabow: Implementation of algorithms for maximum matching on nonbipartite graphs, Ph.D. thesis, Department of Computer Science, Stanford University 1973."},{"key":"2960_CR16","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1016\/j.orl.2004.09.005","volume":"33","author":"D. Gamarnik","year":"2005","unstructured":"D. Gamarnik, M. Lewenstein and M. Sviridenko: An improved upper bound for the TSP in cubic 3-edge-connected graphs, Operations Research Letters 33 (2005), 467\u2013474.","journal-title":"Operations Research Letters"},{"key":"2960_CR17","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"M. R. Garey","year":"1976","unstructured":"M. R. Garey, D. S. Johnson and R. E. Tarjan: The planar Hamiltonian circuit problem is NP-complete, SIAM Journal on Computing 5 (1976), 704\u2013714.","journal-title":"SIAM Journal on Computing"},{"key":"2960_CR18","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0167-6377(91)90016-I","volume":"10","author":"J. A. Hoogeveen","year":"1991","unstructured":"J. A. Hoogeveen: Analysis of Christofides\u2019 heuristic: some paths are more difficult than cycles, Operations Research Letters 10 (1991), 291\u2013295.","journal-title":"Operations Research Letters"},{"key":"2960_CR19","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1145\/174652.174654","volume":"41","author":"S. Khuller","year":"1994","unstructured":"S. Khuller and U. Vishkin: Biconnectivity approximations and graph carvings, Journal of the ACM 41 (1994), 214\u2013235.","journal-title":"Journal of the ACM"},{"key":"2960_CR20","first-page":"289","volume":"17","author":"M. Lorea","year":"1975","unstructured":"M. Lorea: Hypergraphes et matro\u00efdes, Cahiers du Centre d\u2019\u00c9tudes de Recherche Op\u00e9rationelle 17 (1975), 289\u2013291.","journal-title":"Cahiers du Centre d\u2019\u00c9tudes de Recherche Op\u00e9rationelle"},{"key":"2960_CR21","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/BF01894789","volume":"21","author":"L. Lov\u00e1sz","year":"1970","unstructured":"L. Lov\u00e1sz: A generalization of K\u0151nig\u2019s theorem, Acta Mathematica Academiae Scientiarum Hungaricae 21 (1970), 443\u2013446.","journal-title":"Acta Mathematica Academiae Scientiarum Hungaricae"},{"key":"2960_CR22","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/BF01902352","volume":"26","author":"L. Lov\u00e1sz","year":"1975","unstructured":"L. Lov\u00e1sz: 2-matchings and 2-covers of hypergraphs, Acta Mathematica Academiae Scientiarum Hungaricae 26 (1975), 433\u2013444.","journal-title":"Acta Mathematica Academiae Scientiarum Hungaricae"},{"key":"2960_CR23","volume-title":"Matching Theory","author":"L. Lov\u00e1sz","year":"1986","unstructured":"L. Lov\u00e1sz and M. D. Plummer: Matching Theory, Akad\u00e9miai Kiad\u00f3, Budapest 1986, and North-Holland, Amsterdam 1986."},{"key":"2960_CR24","first-page":"560","volume-title":"Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science","author":"T. M\u00f6mke","year":"2011","unstructured":"T. M\u00f6mke and O. Svensson: Approximating graphic TSP by matchings, Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (2011), 560\u2013569."},{"key":"2960_CR25","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF01585735","volume":"46","author":"C. L. Monma","year":"1990","unstructured":"C. L. Monma, B. S. Munson and W. R. Pulleyblank: Minimum-weight twoconnected spanning networks, Mathematical Programming 46 (1990), 153\u2013171.","journal-title":"Mathematical Programming"},{"key":"2960_CR26","first-page":"30","volume-title":"Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science","author":"M. Mucha","year":"2012","unstructured":"M. Mucha: 13\/9-approximation for graphic TSP, Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science (2012), 30\u201341."},{"key":"2960_CR27","first-page":"550","volume-title":"Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science","author":"S. O. Gharan","year":"2011","unstructured":"S. Oveis Gharan, A. Saberi and M. Singh: A randomized rounding approach to the traveling salesman problem, Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (2011), 550\u2013559."},{"key":"2960_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C. H. Papadimitriou","year":"1993","unstructured":"C. H. Papadimitriou and M. Yannakakis: The traveling salesman problem with distances one and two, Mathematics of Operations Research 18 (1993), 1\u201312.","journal-title":"Mathematics of Operations Research"},{"key":"2960_CR29","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1093\/qmath\/os-13.1.83","volume":"13","author":"R. Rado","year":"1942","unstructured":"R. Rado: A theorem on independence relations, Quarterly Journal of Mathematics 13 (1942), 83\u201389.","journal-title":"Quarterly Journal of Mathematics"},{"key":"2960_CR30","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1007\/978-3-642-36694-9_31","volume-title":"Integer Programming and Combinatorial Optimization","author":"A. Seb\u0151","year":"2013","unstructured":"A. Seb\u0151: Eight fifth approximation for TSP paths, in: Integer Programming and Combinatorial Optimization; Proceedings of the 16th IPCO Conference; LNCS 7801 (J. Correa, M.X. Goemans, eds.), Springer, Berlin 2013, 362\u2013374."},{"key":"2960_CR31","first-page":"1","volume":"90","author":"J. Vygen","year":"2012","unstructured":"J. Vygen: New approximation algorithms for the TSP, OPTIMA 90 (2012), 1\u201312.","journal-title":"OPTIMA"},{"key":"2960_CR32","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1090\/S0002-9947-1932-1501641-2","volume":"34","author":"H. Whitney","year":"1932","unstructured":"H. Whitney: Non-separable and planar graphs, Transactions of the American Mathematical Society 34 (1932), 339\u2013362.","journal-title":"Transactions of the American Mathematical Society"},{"key":"2960_CR33","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BFb0120913","volume":"13","author":"L. A. Wolsey","year":"1980","unstructured":"L. A. Wolsey: Heuristic analysis, linear programming and branch and bound, Mathematical Programming Study 13 (1980), 121\u2013134.","journal-title":"Mathematical Programming Study"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-014-2960-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-014-2960-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-014-2960-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T01:32:50Z","timestamp":1559093570000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-014-2960-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10]]},"references-count":33,"aliases":["10.1007\/s00493-011-2960-3"],"journal-issue":{"issue":"5","published-print":{"date-parts":[[2014,10]]}},"alternative-id":["2960"],"URL":"https:\/\/doi.org\/10.1007\/s00493-014-2960-3","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10]]}}}