On the empirical time complexity of finding optimal solutions vs proving optimality for Euclidean TSP instances

DOI10.1007/s11590-014-0828-5zbMath1331.90067OpenAlexW1983531822WikidataQ59585904 ScholiaQ59585904MaRDI QIDQ497453

Holger H. Hoos, Thomas Stützle

Publication date: 24 September 2015

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-014-0828-5

zbMATH Keywords

TSPexact algorithmsempirical complexity

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items

A covering traveling salesman problem with profit in the last mile delivery

Uses Software

• TSPLIB
• LKH
• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem
• On the power of clause-learning SAT solvers as resolution engines
• General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic
• The traveling salesman. Computational solutions for RSP applications
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• Exponential Lower Bounds on the Lengths of Some Classes of Branch-and-Cut Proofs