Probabilistic Analysis of Edge Elimination for Euclidean TSP

MaRDI QIDQ6307383zbMATH OpenFDO

Authors Xianghui Zhong

Publication date 27 September 2018

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Analysis of algorithms (68W40)

Abstract: One way to speed up the calculation of optimal TSP tours in practice is eliminating edges that are certainly not in the optimal tour as a preprocessing step. In order to do so several edge elimination approaches have been proposed in the past. In this work we investigate two of them in the scenario where the input consists of $n$ independently distributed random points in the 2-dimensional unit square with bounded density function from above and below by arbitrary positive constants. We show that after the edge elimination procedure of Hougardy and Schroeder the expected number of remaining edges is $Theta(n)$, while after that the the non-recursive part of Jonker and Volgenant the expected number of remaining edges is $Theta(n^2)$.

This page was built for publication: Probabilistic Analysis of Edge Elimination for Euclidean TSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6307383)