Geodesic
Parameter optimisation of the polynomial randomised algorithm for the asymmetric travelling salesman problem
Journal of the Belarusian State University. Mathematics and Informatics, Tome 2 (2024), pp. 113-118.

Voir la notice de l'article provenant de la source Math-Net.Ru

The asymmetric travelling salesman problem without metric restrictions is herein considered. The polynomial randomised algorithm depending on the set of parameters is proposed similar to the one developed by the author in the article «Polinomial randomised algorithm for the asymmetric travelling salesman problem» (Doklady of the National Academy of Sciences of Belarus. 2022. Vol. 66, No. 5. P. 489-494). The difference of the proposed algorithm is in different parametrisation. The parameter optimisation is arranged with the help of the polynomial preprocessing algorithm.
Keywords: combinatorial optimisation; probability theory; randomised algorithm; approximation algorithm; asymmetric travelling salesman problem 
@article{BGUMI_2024_2_a9,
     author = {M. S. Barketau},
     title = {Parameter optimisation of the polynomial randomised algorithm for the asymmetric travelling salesman problem},
     journal = {Journal of the Belarusian State University. Mathematics and Informatics},
     pages = {113--118},
     publisher = {mathdoc},
     volume = {2},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/BGUMI_2024_2_a9/}
}
TY  - JOUR
AU  - M. S. Barketau
TI  - Parameter optimisation of the polynomial randomised algorithm for the asymmetric travelling salesman problem
JO  - Journal of the Belarusian State University. Mathematics and Informatics
PY  - 2024
SP  - 113
EP  - 118
VL  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/BGUMI_2024_2_a9/
LA  - ru
ID  - BGUMI_2024_2_a9
ER  - 
%0 Journal Article
%A M. S. Barketau
%T Parameter optimisation of the polynomial randomised algorithm for the asymmetric travelling salesman problem
%J Journal of the Belarusian State University. Mathematics and Informatics
%D 2024
%P 113-118
%V 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/BGUMI_2024_2_a9/
%G ru
%F BGUMI_2024_2_a9
M. S. Barketau. Parameter optimisation of the polynomial randomised algorithm for the asymmetric travelling salesman problem. Journal of the Belarusian State University. Mathematics and Informatics, Tome 2 (2024), pp. 113-118. http://geodesic.mathdoc.fr/item/BGUMI_2024_2_a9/

[1] M. S. Barketau, “Polynomial randomised algorithm for the asymmetric travelling salesman problem”, Doklady of the National Academy of Sciences of Belarus, 66(5) (2022), 489–494 | DOI

[2] S. Arora, “Polynomial time approximation schemes for Euclidean TSP and other geometric problems”, Proceedings of 37th Annual symposium on foundations of computer science (Burlington, USA), IEEE Computer Society Press, Los Alamitos, 1996, 2–11 | DOI

[3] O. Svensson, “Approximating ATSP by relaxing connectivity”, Proceedings of 2015 IEEE 56th Annual symposium on foundations of computer science (FOCS-2015) (Berkeley, USA), Conference Publishing Services of the IEEE Computer Society, Los Alamitos, 2015, 1–19 | DOI

[4] E. K. Burke, P. I. Cowling, R. Keuthen, “Effective local and guided variable neighbourhood search methods for the asymmetric travelling salesman problem”, Applications of evolutionary computing. EvoWorkshops-2001. EvoCOP, EvoFlight, EvoIASP, EvoLearn, and EvoSTIM (Como, Italy), Springer, Berlin, 2001, 203–212 (Lecture notes in computer science; volume 2037) | DOI

[5] M. Fischetti, A. Lodi, P. Toth, “Exact methods for the asymmetric traveling salesman problem”, The traveling salesman problem and its variations, Springer, New York, 2007, 169–205 (Combinatorial optimization; volume 12) | DOI

[6] M. Grotschel, L. Lovasz, A. Schrijver, Geometric algorithms and combinatorial optimization. 2nd edition, Algorithms and combinatorics, 2, Springer-Verlag, Berlin, 2012, XII+362 pp.