Abstract:
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
Fulltext:
PDF file (1010 kB)