A novel feature-based approach to characterize algorithm performance for the traveling salesperson problem

Mersmann Olaf, Bischl Bernd,Trautmann Heike, Wagner Markus, Bossek Jakob, Neumann Frank


Abstract
Meta-heuristics are frequently used to tackle NP-hard combinatorial optimization problems. With this paper we contribute to the understanding of the success of 2-opt based local search algorithms for solving the traveling salesperson problem (TSP). Although 2-opt is widely used in practice, it is hard to understand its success from a theoretical perspective. We take a statistical approach and examine the features of TSP instances that make the problem either hard or easy to solve. As a measure of problem difficulty for 2-opt we use the approximation ratio that it achieves on a given instance. Our investigations point out important features that make TSP instances hard or easy to be approximated by 2-opt. © 2013 Springer Science+Business Media Dordrecht.



Publication type
Article in Journal

Peer reviewed
Yes

Publication status
Published

Year
2013

Journal
Annals of Mathematics and Artificial Intelligence

Volume
69

Issue
2

Start page
182

Pages range
151-182

Language
English

ISSN
10122443

DOI

Affiliation
Universitat Dortmund,University of Adelaide