The Library
On the asymptotic behavior of subtour-patching heuristics in solving the TSP on permuted Monge matrices
Tools
Tools
Tools
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, 17 (1). pp. 61-96. doi:10.1007/s10732-010-9127-1
Research output not available from this repository, contact author.
Official URL: http://dx.doi.org/10.1007/s10732-010-9127-1
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 | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences Faculty of Social Sciences > Warwick Business School |
||||
| Library of Congress Subject Headings (LCSH): | Traveling salesman problem, Heuristic algorithms, Matrices | ||||
| Journal or Publication Title: | Journal of Heuristics | ||||
| Publisher: | Springer New York LLC | ||||
| ISSN: | 1381-1231 | ||||
| Official Date: | February 2011 | ||||
| Dates: |
|
||||
| Volume: | 17 | ||||
| Number: | 1 | ||||
| Page Range: | pp. 61-96 | ||||
| DOI: | 10.1007/s10732-010-9127-1 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Funder: | Engineering and Physical Sciences Research Council (EPSRC), Natural Sciences and Engineering Research Council of Canada (NSERC), University of Warwick. Centre for Discrete Mathematics and Its Applications, Universiṭat Ben-Guryon ba-Negev |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
