Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
An Experimental Evaluation of the Best-of-Many Christofides’ Algorithm for the Traveling Salesman Problem
verfasst von : Kyle Genova, David P. Williamson
Erschienen in: Algorithms - ESA 2015
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Recent papers on approximation algorithms for the traveling salesman problem (TSP) have given a new variant on the well-known Christofides’ algorithm for the TSP, called the
Best-of-Many Christofides’ algorithm
. The algorithm involves sampling a spanning tree from the solution to the standard LP relaxation of the TSP, and running Christofides’ algorithm on the sampled tree. In this paper we perform an experimental evaluation of the Best-of-Many Christofides’ algorithm to see if there are empirical reasons to believe its performance is better than that of Christofides’ algorithm. In our experiments, all of the implemented variants of the Best-of-Many Christofides’ algorithm perform significantly better than Christofides’ algorithm; an algorithm that samples from a maximum entropy distribution over spanning trees seems to be particularly good.