On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem

DOI10.1016/j.ejor.2014.03.042zbMath1338.90341OpenAlexW1970822112WikidataQ59585957 ScholiaQ59585957MaRDI QIDQ296693

Holger H. Hoos, Thomas Stützle

Publication date: 23 June 2016

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2014.03.042

zbMATH Keywords

travelling salesman problemcombinatorial optimisationconcordeempirical scaling analysis

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

On the empirical time complexity of finding optimal solutions vs proving optimality for Euclidean TSP instances, A credibilistic goal programming model for inventory routing problem with hazardous materials, Analyzing the performance of TSP solver methods

Uses Software

• TSPLIB
• Concorde
• DIMACS
• bootstrap

Cites Work

• Algorithm runtime prediction: methods \& evaluation
• Certification of an optimal TSP tour through 85,900 cities
• The Euclidean traveling salesman problem is NP-complete
• The traveling salesman. Computational solutions for RSP applications
• A novel feature-based approach to characterize algorithm performance for the traveling salesperson problem
• The searching over separators strategy to solve some NP-hard problems in subexponential time
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item