{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:15:48Z","timestamp":1781345748187,"version":"3.54.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[1995,7,1]],"date-time":"1995-07-01T00:00:00Z","timestamp":804556800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1995,7]]},"DOI":"10.1007\/bf01585563","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T08:42:17Z","timestamp":1114677737000},"page":"335-349","source":"Crossref","is-referenced-by-count":51,"title":["Worst-case comparison of valid inequalities for the TSP"],"prefix":"10.1007","volume":"69","author":[{"given":"Michel X.","family":"Goemans","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"CR1","volume-title":"\u201cFinding cuts in the TSP,\u201d DIMACS Technical Report 95-05","author":"D. Applegate","year":"1995","unstructured":"D. Applegate, R. Bixby, V. Chv\u00e1tal and W. Cook, \u201cFinding cuts in the TSP,\u201d DIMACS Technical Report 95-05, Rutgers University, New Brunswick, NJ, 1995."},{"key":"CR2","volume-title":"Graphes et Hypergraphes","author":"C. Berge","year":"1970","unstructured":"C. Berge,Graphes et Hypergraphes (Dunod, Paris, 1970)."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1287\/moor.16.2.259","volume":"16","author":"S. Boyd","year":"1991","unstructured":"S. Boyd and W. Cunningham, \u201cSmall traveling salesman polytopes,\u201dMathematics of Operations Research 16 (1991) 259\u2013271.","journal-title":"Mathematics of Operations Research"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/BF01588786","volume":"49","author":"S.C. Boyd","year":"1991","unstructured":"S.C. Boyd and W.R. Pulleyblank, \u201cOptimizing over the subtour polytope of the travelling salesman problem,\u201dMathematical Programming 49 (1991) 163\u2013187.","journal-title":"Mathematical Programming"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF01580109","volume":"5","author":"V. Chv\u00e1tal","year":"1973","unstructured":"V. Chv\u00e1tal, \u201cEdmonds polytopes and weakly Hamiltonian graphs,\u201dMathematical Programming 5 (1973) 29\u201340.","journal-title":"Mathematical Programming"},{"key":"CR6","first-page":"291","volume-title":"Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference","author":"J.-M. Clochard","year":"1993","unstructured":"J.-M. Clochard and D. Naddef, \u201cUsing path inequalities in a branch and cut code for the traveling salesman problem,\u201d in: G. Rinaldi and L.A. Wolsey, eds.,Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference (CORE, Louvain-la-Neuve, 1993) pp. 291\u2013311."},{"key":"CR7","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, \u201cThe traveling salesman problem on a graph and some related integer polyhedra,\u201dMathematical Programming 33 (1985) 1\u201327.","journal-title":"Mathematical Programming"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1287\/mnsc.26.5.495","volume":"26","author":"H. Crowder","year":"1980","unstructured":"H. Crowder and M. Padberg, \u201cSolving large-scale symmetric traveling salesman problems to optimality,\u201dManagement Science 26 (1980) 495\u2013509.","journal-title":"Management Science"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF01580734","volume":"40","author":"B. Fleischmann","year":"1988","unstructured":"B. Fleischmann, \u201cA new class of cutting planes for the symmetric traveling salesman problem,\u201dMathematical Programming 40 (1988) 225\u2013246.","journal-title":"Mathematical Programming"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/BF01585700","volume":"53","author":"J. Fonlupt","year":"1992","unstructured":"J. Fonlupt and D. Naddef, \u201cThe traveling salesman problem in graphs with some excluded minors,\u201dMathematical Programming 53 (1992) 147\u2013172.","journal-title":"Mathematical Programming"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF01580607","volume":"60","author":"M.X. Goemans","year":"1993","unstructured":"M.X. Goemans and D. Bertsimas, \u201cSurvivable networks, linear programming relaxations and the parsimonious property,\u201dMathematical Programming 60 (1993) 145\u2013166.","journal-title":"Mathematical Programming"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1287\/moor.5.2.285","volume":"5","author":"M. Gr\u00f6tschel","year":"1980","unstructured":"M. Gr\u00f6tschel, \u201cOn the monotone symmetric travelling salesman problem: hypohamiltonian\/hypotraceable graphs and facets,\u201dMathematics of Operations Research 5 (1980) 285\u2013292.","journal-title":"Mathematics of Operations Research"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BFb0120887","volume":"12","author":"M. Gr\u00f6tschel","year":"1980","unstructured":"M. Gr\u00f6tschel, \u201cOn the symmetric traveling salesman problem: solution of a 120-city problem,\u201dMathematical Programming Study 12 (1980) 61\u201377.","journal-title":"Mathematical Programming Study"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF01586932","volume":"51","author":"M. Gr\u00f6tschel","year":"1991","unstructured":"M. Gr\u00f6tschel and O. Holland, \u201cSolution of large-scale symmetric traveling salesman problems,\u201dMathematical Programming 51 (1991) 141\u2013202.","journal-title":"Mathematical Programming"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01582116","volume":"16","author":"M. Gr\u00f6tschel","year":"1979","unstructured":"M. Gr\u00f6tschel and M.W. Padberg, \u201cOn the symmetric travelling salesman problem I: inequalities,\u201dMathematical Programming 16 (1979) 265\u2013280.","journal-title":"Mathematical Programming"},{"key":"CR16","first-page":"251","volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1985","unstructured":"M. Gr\u00f6tschel and M.W. Padberg, \u201cPolyhedral theory,\u201d in: E. Lawler, J. Lenstra, A. Rinnooy Kan and D. Shmoys, eds.,The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (Wiley, New York, 1985) pp. 251\u2013305."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1287\/moor.11.4.537","volume":"11","author":"M. Gr\u00f6tschel","year":"1986","unstructured":"M. Gr\u00f6tschel and W.R. Pulleyblank, \u201cClique tree inequalities and the symmetric traveling salesman problem,\u201dMathematics of Operations Research 11 (1986) 537\u2013569.","journal-title":"Mathematics of Operations Research"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M. Held","year":"1970","unstructured":"M. Held and R.M. Karp, \u201cThe traveling-salesman and minimum cost spanning trees,\u201dOperations Research 18 (1970) 1138\u20131162.","journal-title":"Operations Research"},{"key":"CR19","unstructured":"M. J\u00fcnger, G. Reinelt and S. Thienel, \u201cProvably good solutions for the traveling salesman problem,\u201d Report 92.114, Institut f\u00fcr Informatik, Universit\u00e4t zu K\u00f6ln, 1992."},{"key":"CR20","unstructured":"J. Lee and W.D. Morris, \u201cGeometric comparison of combinatorial polytopes,\u201d CORE Discussion Paper 9216, CORE, Universit\u00e9 Catholique de Louvain, 1992."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF01585735","volume":"46","author":"C. Monma","year":"1990","unstructured":"C. Monma, B. Munson and W. Pulleyblank, \u201cMinimum-weight two-connected spanning networks,\u201dMathematical Programming 46 (1990) 153\u2013171.","journal-title":"Mathematical Programming"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"882","DOI":"10.1287\/moor.17.4.882","volume":"17","author":"D. Naddef","year":"1992","unstructured":"D. Naddef, \u201cThe binested inequalities for the symmetric traveling salesman polytope,\u201dMathematics of Operations Research 17 (1992) 882\u2013900.","journal-title":"Mathematics of Operations Research"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/BF01586945","volume":"51","author":"D. Naddef","year":"1991","unstructured":"D. Naddef and G. Rinaldi, \u201cThe symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities,\u201dMathematical Programming 51 (1991) 359\u2013400.","journal-title":"Mathematical Programming"},{"key":"CR24","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1287\/moor.17.2.308","volume":"17","author":"D. Naddef","year":"1992","unstructured":"D. Naddef and G. Rinaldi, \u201cThe crown inequalities for the symmetric traveling salesman polytope,\u201dMathematics of Operations Research 17 (1992) 308\u2013326.","journal-title":"Mathematics of Operations Research"},{"key":"CR25","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/BF01581259","volume":"58","author":"D. Naddef","year":"1993","unstructured":"D. Naddef and G. Rinaldi, \u201cThe graphical relaxation: A new framework for the symmetric traveling salesman polytope,\u201dMathematical Programming 58 (1993) 53\u201387.","journal-title":"Mathematical Programming"},{"key":"CR26","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/BFb0120888","volume":"12","author":"M.W. Padberg","year":"1980","unstructured":"M.W. Padberg and S. Hong, \u201cOn the symmetric travelling salesman problem: A computational study,\u201dMathematical Programming Study 12 (1980) 78\u2013107.","journal-title":"Mathematical Programming Study"},{"key":"CR27","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF01580861","volume":"47","author":"M. Padberg","year":"1990","unstructured":"M. Padberg and G. Rinaldi, \u201cFacet identification for the symmetric traveling salesman polytope,\u201dMathematical Programming 47 (1990) 219\u2013257.","journal-title":"Mathematical Programming"},{"key":"CR28","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1137\/1033004","volume":"33","author":"M. Padberg","year":"1991","unstructured":"M. Padberg and G. Rinaldi, \u201cA branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems,\u201dSIAM Review 33 (1991) 60\u2013100.","journal-title":"SIAM Review"},{"key":"CR29","series-title":"Handbooks in Operations Research and Management Science","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/S0927-0507(89)01006-6","volume-title":"Optimization","author":"W. Pulleyblank","year":"1989","unstructured":"W. Pulleyblank, \u201cPolyhedral combinatorics,\u201d in: G. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd, eds.,Optimization, Handbooks in Operations Research and Management Science, Vol. 1 (North-Holland, Amsterdam, 1989) pp. 371\u2013446."},{"key":"CR30","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0020-0190(90)90028-V","volume":"35","author":"D.B. Shmoys","year":"1990","unstructured":"D.B. Shmoys and D.P. Williamson, \u201cAnalyzing the Held-Karp TSP bound: A monotonicity property with application,\u201dInformation Processing Letters 35 (1990) 281\u2013285.","journal-title":"Information Processing Letters"},{"key":"CR31","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BFb0120913","volume":"13","author":"L.A. Wolsey","year":"1980","unstructured":"L.A. Wolsey, \u201cHeuristic analysis, linear programming and branch and bound,\u201dMathematical Programming Study 13 (1980) 121\u2013134.","journal-title":"Mathematical Programming Study"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585563.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01585563\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585563","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T15:32:29Z","timestamp":1556897549000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01585563"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,7]]},"references-count":31,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1995,7]]}},"alternative-id":["BF01585563"],"URL":"https:\/\/doi.org\/10.1007\/bf01585563","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,7]]}}}