| Article ID: | iaor1991291 |
| Country: | Netherlands |
| Volume: | 44 |
| Issue: | 3 |
| Start Page Number: | 410 |
| End Page Number: | 413 |
| Publication Date: | Feb 1990 |
| Journal: | European Journal of Operational Research |
| Authors: | Jeromin Bernd, Krner Frank |
The algorithm of Christofides is considered for the determination of a lower bound for the traveling salesman problem. There exist many investigations for improving this bound. But these are only heuristic proposals. It is shown that the subgradients of the bound function can be easily calculated, and a subgradient procedure is developed for computing a sharp bound.