Improved lower bounds to the travelling salesman problem

Free Access

Issue		RAIRO-Oper. Res. Volume 12, Number 4, 1978


Page(s)		369 - 382
DOI		https://doi.org/10.1051/ro/1978120403691
Published online		06 February 2017

1. M. BELLMORE and J. C. MALONE, Palhology of the Travelling Salesman Subtour Elimination Algorithms, Ops. Res, Vol. 19, 1971, pp. 278-307. [MR: 391976] [Zbl: 0219.90032] [Google Scholar]
2. M. BELLMORE and G. L. NEMHAUSER, The Travelling Salesman Problem : a Survey, Ops. Res., Vol. 16, 1968, p. 538-558. [MR: 234711] [Zbl: 0213.44604] [Google Scholar]
3.N. CHRISTOFIDES, Graph Theory : an Algorithmic Approach, 1975, Academic Press, N.Y., pp. 236-280. [MR: 429612] [Zbl: 0321.94011] [Google Scholar]
4.G. D'ATRI, Lagrangean Relaxation in Integer Programming, IXth Symposium on Mathematical Programming, 1976, Budapest. [Google Scholar]
5.E. W. DIJKISTRA, A Note on Two Problems in Connection with Graphs, Numerische Math., Vol. 1, 1959, pp. 269-173. [EuDML: 131436] [MR: 107609] [Zbl: 0092.16002] [Google Scholar]
6.J. EDMONDS, Some Well Solved Problems in Combinatorial Optimization in Combinatorial Programming : Methods and Applications, 1975, B. ROY, éd., Reidel Pub. Co., pp. 285-311. [MR: 401136] [Zbl: 0312.90037] [Google Scholar]
7.J. EDMONDS and E. JOHNSON, Matching : a Well Solved Class of Integer Linear Programs in Combinatorial Structures and their Applications, 1970, Gordon and Breach, N.Y., pp. 89-92. [MR: 267898] [Zbl: 0258.90032] [Google Scholar]
8. M. L. FISHER, W. D. NORTHUP and J. F. SHAPIRO, Using Duality to Solve Discrete Optimization Problems : Theory and Computational Experience, Math. Prog. Study, Vol. 3, 1975, pp. 56-94. [MR: 444006] [Zbl: 0367.90087] [Google Scholar]
9. A. M. GEOFFRION, Lagrangean Relaxation for Integer Programming, Math. Prog. Study, Vol. 2, 1974, pp. 82-114. [MR: 439172] [Zbl: 0395.90056] [Google Scholar]
10. M. HELD. P. WOLFE and H. P. CROWDER, Validation of Subgradiant Optimization, Math. Prog., Vol. 6, 1974, pp. 62-88. [MR: 341863] [Zbl: 0284.90057] [Google Scholar]
11. M. GONDRAN and J. L. LAURIÈRE, Un Algorithme pour les Problèmes de Recouvrements, R.A.I.R.O., Vol. 2, 1975, pp. 33-51. [EuDML: 104616] [MR: 456455] [Zbl: 0325.90043] [Google Scholar]
12. M. HELD and R. M. KARP, The Travelling Salesman Problem and Minimum Spanning Trees, Ops. Res., Vol. 18, 1970, pp. 1138-1162. [MR: 278710] [Zbl: 0226.90047] [Google Scholar]
13. M. HELD and R. M. KARP, The Travelling Salesman Problem and Minimum Spanning Trees, II, Math. Prog., Vol. 1, 1971, pp. 6-25. [MR: 289119] [Zbl: 0232.90038] [Google Scholar]
14. K. HELBIG HANSEN and J. KRARUP, Improvements of the Held-Karp Algorithm for the Symmetric Travelling Salesman Problem, Math. Prog., Vol. 7, 1974, pp. 87-96. [MR: 359322] [Zbl: 0285.90055] [Google Scholar]
15. J. B. KRUSKAL, On the Shortest Spanning Subtree of a Graph and the Travelling Salesman Problem, Proc. Amer. Math. Soc., Vol. 2, 1956, pp. 48-50. [MR: 78686] [Zbl: 0070.18404] [Google Scholar]
16. S. LIN, Computer Solutions of the Travelling Salesman Problem, Bell System Techn. J., Vol. 44, 1965, pp. 2245-2269. [MR: 189224] [Zbl: 0136.14705] [Google Scholar]
17. S. LIN and B. W. KERNIGHAN, An Effective Heuristic Algorithm for the Travelling Salesman Problem, Ops. Res., Vol. 21, 1973, pp. 498-516. [MR: 359742] [Zbl: 0256.90038] [Google Scholar]
18. J. D. LITTLE et al., An Algorithm for the Travelling Sales Man Problem, Ops. Res., Vol. 11, 1963, pp. 972-989. [Zbl: 0161.39305] [Google Scholar]
19. P. MILIOTIS, Integer Programming Approaches to the Travelling Salesman Problem, Math Prog., Vol. 10, 1976, pp. 367-378. [MR: 441337] [Zbl: 0337.90041] [Google Scholar]
20. C. YAO, An O (|E| log log |V|) Algorithm for finding Minimum Spanning Trees, Inf. Proc. Letters, Vol. 4, September 1975, pp. 21-23. [Zbl: 0307.68028] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.