Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood
From MaRDI portal
Publication:1805008
DOI10.1007/BF02253612zbMath0821.90122MaRDI QIDQ1805008
Rainer E. Burkard, Vladimir G. Deǐneko
Publication date: 4 May 1995
Published in: Computing (Search for Journal in Brave)
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Hermitian, skew-Hermitian, and related matrices (15B57) Eulerian and Hamiltonian graphs (05C45)
Related Items
Special cases of travelling salesman problems and heuristics ⋮ Efficiently solvable special cases of hard combinatorial optimization problems ⋮ The exponential multi-insertion neighborhood for the vehicle routing problem with unit demands ⋮ Perspectives of Monge properties in optimization ⋮ A survey of very large-scale neighborhood search techniques ⋮ GENERALISATIONS OF THE GILMORE-GOMORY TRAVELING SALESMAN PROBLEM AND THE GILMORE-GOMORY SCHEME: A SURVEY ⋮ Subclasses of solvable problems from classes of combinatorial optimization problems ⋮ A new ILP-based refinement heuristic for vehicle routing problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The optimum assignments and a new heuristic approach for the traveling salesman problem
- Geometric applications of a matrix-searching algorithm
- A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
- Sequence comparison with mixed convex and concave costs
- A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
- A new heuristic for the traveling salesman problem
- Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem