Polynomial randomized algorithm for the asymmetric travelling salesman problem
https://doi.org/10.29235/1561-8323-2022-66-5-489-494
Abstract
The asymmetric travelling salesman problem without metric restrictions is considered. The randomized algorithm is proposed. It has a certain approximation guarantee and possesses a certain property regarding the probabilities of the tours built. The computational complexity of the algorithm is polynomial and affordable.
About the Author
M. S. Barketau
United Institute of Informatics Problems of the National Academy of Sciences of Belarus
Belarus
Belarus
Barketau Maksim S. – Ph. D. (Physics and Mathematics),
Associate Professor, Senior Researcher
6, Surganov Str., 220012, Minsk
References
1. Arora S. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. Proceedings of 37th Conference on Foundations of Computer Science, 1996, pp. 2–11. https://doi.org/10.1109/sfcs.1996.548458
2. Svensson O. Approximating ATSP by relaxing connectivity. IEEE 56th Annual Symposium on Foundations of Computer Science, 2015, pp. 1–19. https://doi.org/10.1109/focs.2015.10
3. Burke E., Cowling P., Keuthen R. Effective local and guided variable neighbourhood search methods for the asymmetric travelling salesman problem. Workshops on Applications of Evolutionary Computation. Berlin, Heidelberg, 2001, pp. 203– 212. https://doi.org/10.1007/3-540-45365-2_21
4. Fischetti M., Lodi A., Toth P. Exact methods for the asymmetric traveling salesman problem. The traveling salesman problem and its variations. Boston, MA, 2007, pp. 169–205. https://doi.org/10.1007/0-306-48213-4_4
Review
Views: 248
Email this article 