Approximate algorithms for the traveling salesman problem. II

We present several approximate algorithms for solving discrete optimization problems. For instance, for the minimum traveling salesman problem we establish bounds on the functionals for the symmetric problem with a value larger than (99.0–99.70) %; for the asymmetric problem, larger than (99.0–99.23) % (experimental estimates). Besides, we propose a different algorithm for the minimum traveling salesman problem that uses both two-index and single-index models.

Presented by the member of Editorial Board: A. A. Lazarev