×

Analyzing the Held-Karp TSP bound: A monotonicity property with application. (English) Zbl 0698.68050

Summary: In their 1971 paper on the traveling salesman problem and minimum spanning trees, Held and Karp showed that finding an optimally weighted 1-tree is equivalent to solving a linear program for the traveling salesman problem (TSP) with only node-degree constraints and subtour elimination constraints. We show that the Held-Karp 1-trees have a certain monotonicity property: given a particular instance of the symmetric TSP with triangle inequality, the cost of the minimum weighted 1-tree is monotonic with respect to the set of nodes included. As a consequence, we obtain an alternate proof of a result of Wolsey and show that linear programs with node-degree and subtour elimination constraints must have a cost at least (2/3)\({\mathcal O}{\mathcal P}{\mathcal T}\) where \({\mathcal O}{\mathcal P}{\mathcal T}\) is the cost of the optimum solution to the TSP instance.

MSC:

68Q25 Analysis of algorithms and problem complexity
90C35 Programming involving graphs or networks
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Christofides, N., Worst case analysis of a new heuristic for the traveling salesman problem, Rept. 388, (1976), Graduate School of Industrial Administration, Carnegie-Mellon University Pittsburgh, PA
[2] Edmonds, J., Maximum matching and a polyhedron with 0,1-vertices, J. res. nat. bur. standards, 69, 125-130, (1965) · Zbl 0141.21802
[3] M.X. Goemans and D.J. Bertsimas, Probabilistic analysis of the Held and Karp lower bound for the Euclidean traveling salesman problem, Math. Oper. Res., to appear. · Zbl 0733.90072
[4] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric algorithms and combinatorial optimization, (1988), Springer Berlin · Zbl 0634.05001
[5] Grötschel, M.; Padberg, M.W.; Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G.; Shmoys, D.B., Polyhedral theory, The traveling salesman problem, (1985), Wiley Chichester, UK
[6] Held, M.; Karp, R.M., The traveling salesman problem and minimum spanning trees, Oper. res., 18, 1138-1162, (1970) · Zbl 0226.90047
[7] Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G.; Shmoys, D.B., The traveling salesman problem, (1985), Wiley Chichester, UK · Zbl 0563.90075
[8] Padberg, M.W.; Grötschel, M.; Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G.; Shmoys, D.B., Polyhedral computations, The traveling salesman problem, (1985), Wiley Chichester, UK
[9] Williamson, D.P., Analysis of the held-karp heuristic for the traveling salesman problem, S.M. thesis, (1990), Department of Electrical Engineering and Computer Science, MIT Cambridge, MA
[10] Wolsey, L., Heuristic analysis, linear programming, and branch and bound, Math. programming stud., 13, 121-134, (1980) · Zbl 0442.90061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.