Deineko, Vladimir G., Shabtay, Dvir and Steiner, George. (2011) On the asymptotic behavior of subtour-patching heuristics in solving the TSP on permuted Monge matrices. Journal of Heuristics, Vol.17 (No.1). pp. 61-96. ISSN 1381-1231

Full text not available from this repository.

Abstract

We examine the performance of different subtour-patching heuristics for solving the strongly NP-hard traveling salesman problem (TSP) on permuted Mange matrices. We prove that a well-known heuristic is asymptotically optimal for the TSP on product matrices and k-root cost matrices. We also show that the heuristic is provably asymptotically optimal for general permuted Monge matrices under some mild conditions. Our theoretical results are strongly supported by the findings of a large-scale experimental study on randomly generated numerical examples, which show that the heuristic is not only asymptotically optimal, but also finds optimal TSP tours with high probability that increases with the problem size. Thus the heuristic represents a practical tool to solve large instances of the problem.

Item Type:	Journal Article
Divisions:	Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences Faculty of Social Sciences > Warwick Business School
Journal or Publication Title:	Journal of Heuristics
Publisher:	Springer New York LLC
ISSN:	1381-1231
Date:	February 2011
Volume:	Vol.17
Number:	No.1
Page Range:	pp. 61-96
Identification Number:	10.1007/s10732-010-9127-1
Status:	Peer Reviewed
Publication Status:	Published
Funder:	Centre for Discrete Mathematics and Its Applications, University of Warwick , Engineering and Physical Sciences Research Council (EPRSC) UK , Paul Ivanier Center for Robotics and Production Management, Ben-Gurion University of the Negev , Natural Sciences and Engineering Research Council of Canada
URI:	http://wrap.warwick.ac.uk/id/eprint/41652

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item