Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

Request Changes to record.

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:
DateEvent
February 2011Published
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 View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us