Some Examples of Difficult Traveling Salesman Problems

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Applications of graph theory to circuits and networks (94C15)

Cited In (26)

Scheduling Large-Scale Advance-Request Dial-A-Ride Systems
Hill Climbing with Multiple Local Optima
On the refinement of bounds of heuristic algorithms for the traveling salesman problem
Change ringing and Hamiltonian cycles: the search for Erin and Stedman triples
A polynomial-time solution to Papadimitriou and Steiglitz's ``traps
On the relationship of approximation algorithms for the minimum and the maximum traveling salesman problem
Optimization, approximation, and complexity classes
An empirical study of a new metaheuristic for the traveling salesman problem
Local search and the local structure of NP-complete problems
How easy is local search?
On the number of iterations of local improvement algorithms
Data-independent neighborhood functions and strict local optima
Polynomial transformations and data-independent neighborhood functions
HAMILTONian circuits in chordal bipartite graphs
On the Hardness of Reoptimization
On minimal Eulerian graphs
Measuring instance difficulty for combinatorial optimization problems
The fleet size and mix vehicle routing problem
Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem
Optimal arcs for the traveling salesman problem
A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems
k-interchange procedures for local search in a precedence-constrained routing problem
An effective implementation of the Lin-Kernighan traveling salesman heuristic
Knowing all optimal solutions does not help for TSP reoptimization
A probabilistic analysis of the switching algorithm for the Euclidean TSP
Traveling salesman problem and local search

This page was built for publication: Some Examples of Difficult Traveling Salesman Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4162995)