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

Sutcliffe, PJ; Solomon, A; Edwards, J

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

Sutcliffe, PJ Solomon, A Edwards, J

Permalink

Publication Type:: Journal Article
Citation:: Computational Optimization and Applications, 2012, 53 (3), pp. 711 - 728
Issue Date:: 2012-12-01

Closed Access

	Filename	Description	Size
	2012000550OK.pdf		654.17 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Sutcliffe, PJ	en_US
dc.contributor.author	Solomon, A	en_US
dc.contributor.author	Edwards, J https://orcid.org/0000-0002-7105-997X	en_US
dc.date.issued	2012-12-01	en_US
dc.identifier.citation	Computational Optimization and Applications, 2012, 53 (3), pp. 711 - 728	en_US
dc.identifier.issn	0926-6003	en_US
dc.identifier.uri	http://hdl.handle.net/10453/22778
dc.description.abstract	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. © 2012 Springer Science+Business Media, LLC.	en_US
dc.relation.ispartof	Computational Optimization and Applications	en_US
dc.relation.isbasedon	10.1007/s10589-012-9472-0	en_US
dc.subject.classification	Operations Research	en_US
dc.title	Computing the variance of tour costs over the solution space of the TSP in polynomial time	en_US
dc.type	Journal Article
utslib.citation.volume	3	en_US
utslib.citation.volume	53	en_US
utslib.for	0103 Numerical and Computational Mathematics	en_US
utslib.for	0102 Applied Mathematics	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Business
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Electrical and Data Engineering
utslib.copyright.status	closed_access
pubs.issue	3	en_US
pubs.publication-status	Published	en_US
pubs.volume	53	en_US

Abstract:

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. © 2012 Springer Science+Business Media, LLC.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/22778