Computing the variance of tour costs over the solution space of the TSP in polynomial time

Publisher:
Springer
Publication Type:
Journal Article
Citation:
Computational Optimization and Applications, 2012, 53 (3), pp. 711 - 728
Issue Date:
2012-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2012000550OK.pdf654.17 kB
Adobe PDF
We give an O(n 2) time algorithm to find the population variance of tour costs over the solution space of the n city symmetric Traveling Salesman Problem (TSP). The algorithm has application in both the stochastic case, where the problem is specified in terms of edge costs which are pairwise independently distributed random variables with known mean and variance, and the numeric edge cost case. We apply this result to provide empirical evidence that, in a range of real world problem sets, the optimal tour cost correlates with a simple function of the mean and variance of tour costs
Please use this identifier to cite or link to this item: