Advanced search
Publication Cover
Optimization
A Journal of Mathematical Programming and Operations Research
Volume 17, 1986 - Issue 1
Submit an article Journal homepage
20
Views
2
CrossRef citations to date
0
Altmetric
Original Articles

Sharp bounds for Karp's “patching”-algorithm for the approximate solution of the traveling salesman problem

B. Jeromin Sektlon Mathematik, Technisehe Universität Dresden, Mommsenstr. 13, Dresden, DDR - 8027
&
F. Körker Sektion Mathematik, Technisehe Hochschule Karl-Marx-Stadt, Reichenhainer Str. 41, Karl-Marx-Stadt, DDR - 9022
Pages 85-92 | Received 01 Feb 1984, Published online: 27 Jun 2007

References

  • Adrabinski , A.A. and Syslo , M.M. 1983 . Computational experiments with some heuristic algorithm for the traveling salesman problem . Zast. Mat , 18 : 91 – 95 .
  • Burkard , R.E. 1979 . Traveling salesman and assignment problems: A survey . Annals of Discr. Math , 4 : 193 – 215 .
  • Christofides , N. 1976 . “ Worst-case analysis of a new heuristic for the traveling salesman problem ” . In GSIA , Carnegie-Melton Univ .
  • Frieze , A.M. , Galbiati , G. and Maffioli , F. 1982 . On the worst-case performance of some algorithms for the asymmetric traveling salesman problem . Networks , 12 : 23 – 39 .
  • Jeromin , B. and Körner , F. 1985 . On the refinement of bounds of heuristic algorithm for the traveling salesman problem . Math. Progr , 82 : 114 – 117 .
  • Jeromin , B. and Körner , F. 1982 . Zur Verschärfung der CHRISTOFIDES-Schranke fur den Wert einer optimalen Tour des Rundreiseproblems . MOS Series Optimization , 13 ( 3 ) : 359 – 371 .
  • Jonker , R. , Kaas , R. and Volgenant , T. 1980 . Data-dependent bounds for heuristics to find a minimum weight Hamiltonian circuit . Oper, Res , 28 ( 3 ) : 1219 – 1222 .
  • Jonker , R. and Volgenant , T. 1982 . Identification of non-optimal arcs for the traveling salesman problem . Oper. Res. Letters , 1 ( 3 ) : 85 – 88 .
  • Kasting , C. 1976 . Integer programming and related areas. A classifield bibliography. LIST in Econ . Math. Systems, Oper. Res , 128 ( 3 )
  • Karp , R.M. 1979 . A patching algorithm for the nonsymmetric traveling salesman problem . SIAM J. Comp , 8 ( 3 )
  • Rosenkrantz , D.J. , Sterns , R.E. and Lewis , P.M. 1977 . An analysis of several heuristics for the traveling salesman problem . SIAM J. Comp , 6 ( 3 ) : 563 – 581 .
  • Sahni , S. and Gonzales , T. 1976 . P-complete approximation problems . J. ACM , 28 ( 3 ) : 555 – 565 .
  • Slominski , L. 1982 . Probabilistic analysis of combinatorial algorithms: A bibliography with selected annotations . Computing , 28 ( 3 ) : 257 – 267 .

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Order Reprints Request Corporate Permissions

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

Request Academic Permissions

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.