This repository provides supporting code and data files for the paper Perturbation Analysis of Practical Algorithms for the Maximum Scatter Travelling Salesman Problem published at ALENEX 2022, co-authored by Emil Biju and Sundar Raman P.
The Maximum Scatter Traveling Salesman Problem (MSTSP) is a variant of the famous Traveling Salesman Problem (TSP) and finds its use in several real-world applications including manufacturing, imaging and laser melting processes. The objective of this problem is to maximize the cost of the least cost edge in a tour of an input graph. Akin to the TSP and several of its variants, the MSTSP is an NP-hard problem. While several approximation algorithms have been proposed for this problem, many of them suffer from bad worst-case complexities and present challenges in scalability and practical use.
In this work, we describe six algorithms for MSTSP inspired by prior work in the area, along with improved formulations that enhance their utility in real-world scenarios. Further, we perform experimental studies motivated by smoothed analysis to comprehensively evaluate these algorithms from the perspective of run-time, quality and stability.