Probabilistic Analysis of the Held and Karp Lower Bound for the Euclidean Traveling Salesman Problem

DOI10.1287/moor.16.1.72zbMath0733.90072OpenAlexW2160442083WikidataQ56067395 ScholiaQ56067395MaRDI QIDQ3360680

Michel X. Goemans, Dimitris J. Bertsimas

Publication date: 1991

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.16.1.72

zbMATH Keywords

polyhedral description1-tree relaxationEuclidean traveling salesmansubadditive Euclidean functionalsHeld-Karp lower bound

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Asymptotics for Euclidean functionals with power-weighted edges, Solving large-scale TSP using a fast wedging insertion partitioning approach, Analyzing the Held-Karp TSP bound: A monotonicity property with application, Scaling laws for maximum coloring of random geometric graphs, Analysis of the Held-Karp lower bound for the asymmetric TSP, Survivable networks, linear programming relaxations and the parsimonious property, A note on relatives to the Held and Karp 1-tree problem, An improved lower bound for the traveling salesman constant, Estimating the Held-Karp lower bound for the geometric TSP, On some approximately balanced combinatorial cooperative games