Improved lower bounds to the travelling salesman problem

Gianfranco d'Atri

RAIRO - Operations Research - Recherche Opérationnelle (1978)

  • Volume: 12, Issue: 4, page 369-382
  • ISSN: 0399-0559

How to cite

top

d'Atri, Gianfranco. "Improved lower bounds to the travelling salesman problem." RAIRO - Operations Research - Recherche Opérationnelle 12.4 (1978): 369-382. <http://eudml.org/doc/104707>.

@article{dAtri1978,
author = {d'Atri, Gianfranco},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
language = {eng},
number = {4},
pages = {369-382},
publisher = {EDP-Sciences},
title = {Improved lower bounds to the travelling salesman problem},
url = {http://eudml.org/doc/104707},
volume = {12},
year = {1978},
}

TY - JOUR
AU - d'Atri, Gianfranco
TI - Improved lower bounds to the travelling salesman problem
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1978
PB - EDP-Sciences
VL - 12
IS - 4
SP - 369
EP - 382
LA - eng
UR - http://eudml.org/doc/104707
ER -

References

top
  1. 1. M. BELLMORE and J. C. MALONE, Palhology of the Travelling Salesman Subtour Elimination Algorithms, Ops. Res, Vol. 19, 1971, pp. 278-307. Zbl0219.90032MR391976
  2. 2. M. BELLMORE and G. L. NEMHAUSER, The Travelling Salesman Problem : a Survey, Ops. Res., Vol. 16, 1968, p. 538-558. Zbl0213.44604MR234711
  3. 3. N. CHRISTOFIDES, Graph Theory : an Algorithmic Approach, 1975, Academic Press, N.Y., pp. 236-280. Zbl0321.94011MR429612
  4. 4. G. D'ATRI, Lagrangean Relaxation in Integer Programming, IXth Symposium on Mathematical Programming, 1976, Budapest. 
  5. 5. E. W. DIJKISTRA, A Note on Two Problems in Connection with Graphs, Numerische Math., Vol. 1, 1959, pp. 269-173. Zbl0092.16002MR107609
  6. 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. Zbl0312.90037MR401136
  7. 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. Zbl0258.90032MR267898
  8. 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. Zbl0367.90087MR444006
  9. 9. A. M. GEOFFRION, Lagrangean Relaxation for Integer Programming, Math. Prog. Study, Vol. 2, 1974, pp. 82-114. Zbl0395.90056MR439172
  10. 10. M. HELD. P. WOLFE and H. P. CROWDER, Validation of Subgradiant Optimization, Math. Prog., Vol. 6, 1974, pp. 62-88. Zbl0284.90057MR341863
  11. 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. Zbl0325.90043MR456455
  12. 12. M. HELD and R. M. KARP, The Travelling Salesman Problem and Minimum Spanning Trees, Ops. Res., Vol. 18, 1970, pp. 1138-1162. Zbl0226.90047MR278710
  13. 13. M. HELD and R. M. KARP, The Travelling Salesman Problem and Minimum Spanning Trees, II, Math. Prog., Vol. 1, 1971, pp. 6-25. Zbl0232.90038MR289119
  14. 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. Zbl0285.90055MR359322
  15. 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. Zbl0070.18404MR78686
  16. 16. S. LIN, Computer Solutions of the Travelling Salesman Problem, Bell System Techn. J., Vol. 44, 1965, pp. 2245-2269. Zbl0136.14705MR189224
  17. 17. S. LIN and B. W. KERNIGHAN, An Effective Heuristic Algorithm for the Travelling Salesman Problem, Ops. Res., Vol. 21, 1973, pp. 498-516. Zbl0256.90038MR359742
  18. 18. J. D. LITTLE et al., An Algorithm for the Travelling Sales Man Problem, Ops. Res., Vol. 11, 1963, pp. 972-989. Zbl0161.39305
  19. 19. P. MILIOTIS, Integer Programming Approaches to the Travelling Salesman Problem, Math Prog., Vol. 10, 1976, pp. 367-378. Zbl0337.90041MR441337
  20. 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. Zbl0307.68028

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.