Some remarks on two degrees of asymmetry in the traveling salesman problem

Bernd Jeromin; Frank Körner

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

  • Volume: 22, Issue: 3, page 301-308
  • ISSN: 0399-0559

How to cite

top

Jeromin, Bernd, and Körner, Frank. "Some remarks on two degrees of asymmetry in the traveling salesman problem." RAIRO - Operations Research - Recherche Opérationnelle 22.3 (1988): 301-308. <http://eudml.org/doc/104945>.

@article{Jeromin1988,
author = {Jeromin, Bernd, Körner, Frank},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {approximation; traveling salesman; bounded heuristic; degree of asymmetry},
language = {eng},
number = {3},
pages = {301-308},
publisher = {EDP-Sciences},
title = {Some remarks on two degrees of asymmetry in the traveling salesman problem},
url = {http://eudml.org/doc/104945},
volume = {22},
year = {1988},
}

TY - JOUR
AU - Jeromin, Bernd
AU - Körner, Frank
TI - Some remarks on two degrees of asymmetry in the traveling salesman problem
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1988
PB - EDP-Sciences
VL - 22
IS - 3
SP - 301
EP - 308
LA - eng
KW - approximation; traveling salesman; bounded heuristic; degree of asymmetry
UR - http://eudml.org/doc/104945
ER -

References

top
  1. 1. N. CHRISTOFIDES, Worst-case Analysis of a New Heuristic for the Traveling Salesman Problem, Carnegie-Mellon Univ., Pittsburgh, 1976. 
  2. 2. W. F. DEMJANOW and W. N. MALOZEMOW, Einführung in Minimax-Probleme, Akad. Verlagsgesellschaft, Geest & Portig, Leipzig, 1975. 
  3. 3. A. M. FRIEZE, G. GALBIATI and F. MAFFIOLI, On the worst-case Performance of some Algorithms for the Asymmetric Traveling Salesman Problem, Networks, Vol. 12, 1982, pp. 23-39. Zbl0478.90070MR667262
  4. 4. B. JEROMIN and F. KÖRNER, Zur Verschärfung der Christofides-Schranke für den Wert einer optimalen Tour des Rundreiseproblems, MOS, Ser. Optimization, Vol. 13, 1982, pp. 359-371. Zbl0505.90051MR668798
  5. 5. B. JEROMIN and F. KÖRNER, On the Refinement of Bounds of Heuristic Algorithms for the Traveling Salesman Problem, Math. Prog., Vol. 32, 1985, pp. 114-117. Zbl0564.90040MR787747
  6. 6. B. JEROMIN and F. KÖRNER, Triangle Inequality and Symmetry in Connection with the Assignment and the Traveling Salesman Problem, Preprint 07-11-87 TU Dresden, to appear in EJOR. Zbl0671.90085MR978495
  7. 7. R. JONKER, R. KAAS and A. VOLGENANT, Datadependent bounds for Heuristics to Find a Minimum weight Hamiltonian Circuit, Oper. Res., Vol. 28, 1980, pp. 1219-1222. Zbl0449.90093MR589682
  8. 8. R. JONKER and T. VOLGENANT, Transforming Asymmetric Into Symmetric Traveling Salesman Problems, Oper. Res. Letters, Vol. 2, 1983, pp. 161-163. Zbl0529.90090MR943039
  9. 9. F. KÖRNER, On the Degree of Asymmetry in the Traveling Salesman Problem, Zast. Mat. Appl. Mat., Vol. 19, 1986, pp. 117-123. Zbl0637.90096MR897519
  10. 10. E. L. LAWLER, J. K. LENSTRA, A. H. G. RINNOOY KAN and D. B. SHMOYS, The Traveling Salesman Problem, John Wiley, Chichester, 1985. Zbl0562.00014MR811467
  11. 11. W. SCHIEBEL, J. TERNO and G. UNGER, Ein Beitrag zur Klassifizierung von Rundreiseproblemen, M.O.S., Ser. Optimization, Vol. 10, 1979, pp. 523-528. Zbl0429.90049MR568629
  12. 12. R. JONKER, Traveling Salesman and Assignment Algorithms: Design and Implementation, Dissertation, Amsterdam, 1986. 
  13. 13. A. VOLGENANT, Contributions to the Solution of the Traveling Salesman Problem and Related Problems, Dissertation, Amsterdam, 1987. 

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.