3/4-approximation Algorithm for the Maximum Three Salesman Problem

Overview

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.

Competition history

• ISEF 2020 Mathematics · Entry MATH004

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.