Abstract:
Some estimates for the optimal quality criterion for the maximum travelling salesman problem are known. These estimates are $\sim75$ % for symmetric problems and $\sim57$ % for asymmetric ones. We propose new estimates: more than $\sim(99.0$–$99.7)$ % for symmetric problems and more than $\sim(99.0$–$99.23)$ % for asymmetric problems. All estimates are obtained by extending the series of problem that occur in the solution of the maximum travelling salesman problem.
Presented by the member of Editorial Board:A. A. Lazarev