Some Examples of Difficult Traveling Salesman Problems

DOI10.1287/opre.26.3.434zbMath0383.90105OpenAlexW2089929819WikidataQ92175892 ScholiaQ92175892MaRDI QIDQ4162995

Kenneth Steiglitz, Christos H. Papadimitriou

Publication date: 1978

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/7487ea033b1729fb7695841673ece0e4782fdb88

Mathematics Subject Classification ID

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

Related Items

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