Booth Id:
MATH004
Category:
Mathematics
Year:
2020
Finalist Names:
Savin, Semen (School: The Orthodox Gymnasium in the name St. Sergius of Radonezh)
Abstract:
We present a polynomial-time approximation Algorithm for the 3-Peripatetic Salesman Problem on maximum (3-PSP-max). The m-Peripatetic Salesman Problem (m-PSP) is a generalization of the classical Travelling Salesman Problem (TSP). The task in m-PSP is to find m edge-disjoint Hamiltonian cycles of maximal or minimal total weight in a complete weighted graph. We prove that our Algorithm for solving 3-PSP-max has guaranteed approximation ratio 3/4 and cubic running-time.
Like many other approximation algorithms for TSP-max and m-PSP-max, our Algorithm builds Hamiltonian cycles from regular subgraphs, cycle covers and partial tours of maximal weight in the input graph. As a part of Algorithm, we implement a modified version of the main procedure from the well-known 3/4 approximate algorithm for TSP-max by Serdyukov. Besides, we apply two other procedures from the previously elaborated algorithms for 2-PSP-max and 2-PSP-min combining them with some new ideas.
The development of polynomial-time approximation algorithms for TSP and m-PSP is motivated by the fact that all non-trivial versions of these problems are NP-hard. The most applicable algorithms with best known guaranteed approximation bounds for m-PSP-max are the following:
1)For 2-PSP-max, the polynomial algorithm with approximation ratio 7/9 by Glebov and Zambalaeva.
2)For 3-PSP-max, the polynomial algorithm with approximation ratio 2/3 by Bykov.
The second algorithm was later improved by the author to a one with approximation ratio 20/27 (2018).
Our Algorithm further improves this ratio to 3/4.
Keywords: m-Perepatetic Salesman Problem, Hamiltonian cycle, Approximation algorithm, guaranteed approximation ratio.