Perturbation Analysis of Practical Algorithms for Maximum Scatter TSP
Published in Symposium on Algorithm Engineering and Experiments (ALENEX22) by Sundar Raman P, Emil Biju, 2022
In this work, we describe six algorithms for MSTSP with improved formulations of prior work that enhance their real-world efficacy. Further, we perform experimental studies motivated by smoothed analysis to comprehensively evaluate these algorithms in terms of run-time, quality and stability.
The six algorithms that we describe in this work are:
- Naive Greedy
- Naive Weave
- Hoffmann Weave
- Dirac
- Pure 2-opt
- Randomized 2-opt
Our benchmarking experiments can be broadly split into three categories:
- Closeness of algorithm predictions to the scatter bound
- Deviation of maximum scatter predictions under perturbation
- Variation in the runtime of algorithms
Key Contributions:
- We observe that the Naive Greedy algorithm is very fast and easy-to-implement baseline for MSTSP.
- We present the Naive Weave and Hoffmann Weave algorithms which introduce an improved formulation of the work by Arkin and Hoffmann to extend their usability to non-regular grids.
- We introduce Pure 2-opt and Randomised 2-opt as very close approximation algorithms for the MSTSP.
- We used a real-world dataset augmented using five graph perturbations and evaluated with three edge cost metrics to perform a comprehensive perturbation analysis of the algorithms and compare results on three critical performance measures, namely, the quality, runtime and stability of the algorithms.