Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey

DOI10.1137/S0036144596297514zbMath1052.90597OpenAlexW2135149549MaRDI QIDQ4210360

Rainer E. Burkard, Vladimir G. Deǐneko, Jack A. A. van der Veen, Gerhard J. Woeginger, René van Dal

Publication date: 21 September 1998

Published in: SIAM Review (Search for Journal in Brave)

Full work available at URL: http://epubs.siam.org:80/sam-bin/dbq/article/29751

zbMATH Keywords

computational complexitycombinatorial optimizationpolynomial time algorithmtraveling salesman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Combinatorial optimization (90C27)

Related Items (63)

Linearizable special cases of the QAP ⋮ Scheduling electric vehicles and locating charging stations on a path ⋮ Gantry crane and shuttle car scheduling in modern rail-rail transshipment yards ⋮ Minimizing the makespan on a single machine subject to modular setups ⋮ On the traveling salesman problem with a relaxed Monge matrix ⋮ Multiobjective traveling salesperson problem on Halin graphs ⋮ Optimal wire ordering and spacing in low power semiconductor design ⋮ Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches ⋮ The Number of Flips Required to Obtain Non-crossing Convex Cycles ⋮ A new mathematical programming formulation for the single-picker routing problem ⋮ A survey on single crane scheduling in automated storage/retrieval systems ⋮ On the Skeleton of the Polytope of Pyramidal Tours ⋮ A (0-1) goal programming model for scheduling the tour of a marketing executive ⋮ On the Euclidean TSP with a permuted van der Veen matrix ⋮ The two-stripe symmetric circulant TSP is in P ⋮ A new asymmetric pyramidally solvable class of the traveling salesman problem ⋮ The quadratic minimum spanning tree problem and its variations ⋮ Approximating the 2-machine flow shop problem with exact delays taking two values ⋮ Pyramidal tours and multiple objectives ⋮ Perspectives of Monge properties in optimization ⋮ Two-machine stochastic flow shops with blocking and the traveling salesman problem ⋮ Some properties of the skeleton of the pyramidal tours polytope ⋮ Arc routing based compact formulations for picker routing in single and two block parallel aisle warehouses ⋮ On the asymptotic behavior of subtour-patching heuristics in solving the TSP on permuted Monge matrices ⋮ Using well-solvable quadratic assignment problems for VLSI interconnect applications ⋮ The multi-stripe travelling salesman problem ⋮ Estimation of Monge matrices ⋮ Crane scheduling in railway yards: an analysis of computational complexity ⋮ A note on the approximation of the asymmetric traveling salesman problem. ⋮ The maximum travelling salesman problem on symmetric Demidenko matrices ⋮ Sequencing situations with just-in-time arrival, and related games ⋮ Minimizing the number of workers in a paced mixed-model assembly line ⋮ Computing an eigenvector of a Monge matrix in max-plus algebra ⋮ Polynomially solvable cases of the bipartite traveling salesman problem ⋮ The \(x\)-and-\(y\)-axes travelling salesman problem ⋮ An exact method for scheduling a yard crane ⋮ An asymmetric analogue of van der Veen conditions and the traveling salesman problem ⋮ Discrete optimization: an Austrian view ⋮ The maximum traveling salesman problem on van der Veen matrices ⋮ GENERALISATIONS OF THE GILMORE-GOMORY TRAVELING SALESMAN PROBLEM AND THE GILMORE-GOMORY SCHEME: A SURVEY ⋮ A method of estimating computational complexity based on input conditions for \(N\)-vehicle problem ⋮ Lexicographically minimizing axial motions for the Euclidean TSP ⋮ Exact algorithms for the order picking problem ⋮ Using well-solvable minimum cost exact covering for VLSI clock energy minimization ⋮ High multiplicity asymmetric traveling salesman problem with feedback vertex set and its application to storage/retrieval system ⋮ Exact and heuristic algorithms for routing AGV on path with precedence constraints ⋮ Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem ⋮ The trouble with the second quantifier ⋮ The computational complexity of the \(k\)-minimum spanning tree problem in graded matrices ⋮ An approximation algorithm for a bottleneck traveling salesman problem ⋮ Three value TSP and linkages with the three value linear spanning 2-forests ⋮ Traveling salesman games with the Monge property ⋮ Clustering analysis of a dissimilarity: a review of algebraic and geometric representation ⋮ THE MAXIMUM TRAVELING SALESMAN PROBLEM ON BANDED MATRICES ⋮ A review of TSP based approaches for flowshop scheduling ⋮ In memoriam: Gerhard Woeginger (1964--2022) ⋮ Four-point conditions for the TSP: the complete complexity classification ⋮ Robotic-cell scheduling: special polynomially solvable cases of the traveling salesman problem on permuted Monge matrices ⋮ SCHEDULING TWO-MACHINE FLOW SHOPS WITH EXACT DELAYS ⋮ New exponential neighbourhood for polynomially solvable TSPs ⋮ An asymmetric analog of van der Veen conditions and the traveling salesman problem. II ⋮ An approximation algorithm with performance guarantees for the maximum traveling salesman problem on special matrices ⋮ New polynomially solvable classes and a new heuristic for the traveling salesman problem and its generalization

This page was built for publication: Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey