scientific article

Paul C. Gilmore, David B. Shmoys, Eugene L. Lawler

Publication date: 1985

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

survey polynomial algorithms travelling salesman circulants Halin graphs subtour patching limited bound widths open Hamiltonian path pyramidal tours

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items (79)

Linearizable special cases of the QAP ⋮ Graphs in which all Hamiltonian cycles have the same length ⋮ A linear time algorithm for the bottleneck traveling salesman problem on a Halin graph ⋮ On the traveling salesman problem with a relaxed Monge matrix ⋮ Monge matrices make maximization manageable ⋮ Multiobjective traveling salesperson problem on Halin graphs ⋮ The Convex-hull-and-k-line Travelling Salesman Problem ⋮ On the Skeleton of the Polytope of Pyramidal Tours ⋮ Some local search algorithms for no-wait flow-shop problem with makespan criterion ⋮ On the recognition of permuted bottleneck Monge matrices ⋮ Different behaviour of a double branch-and-bound algorithm on \(\mathrm {Fm}|\mathrm{prmu}|C_{\max}\) and \(\mathrm {Fm}|\mathrm {block}|C_{\max}\) problems ⋮ Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion ⋮ On the Euclidean TSP with a permuted van der Veen matrix ⋮ A polynomial-time solution to Papadimitriou and Steiglitz's ``traps ⋮ Efficiently solvable special cases of hard combinatorial optimization problems ⋮ The two-stripe symmetric circulant TSP is in P ⋮ A new asymmetric pyramidally solvable class of the traveling salesman problem ⋮ An algorithm for the detection and construction of Monge sequences ⋮ The computational complexity of Steiner tree problems in graded matrices ⋮ Two-stage no-wait scheduling models with setup and removal times separated ⋮ Hamiltonian cycles in circulant digraphs with two stripes ⋮ Pyramidal tours and multiple objectives ⋮ Perspectives of Monge properties in optimization ⋮ Sometimes travelling is easy: The master tour problem ⋮ On the asymptotic behavior of subtour-patching heuristics in solving the TSP on permuted Monge matrices ⋮ Monge properties of sequence alignment ⋮ Two-stage no-wait hybrid flowshop scheduling with inter-stage flexibility ⋮ Efficient filtering for the resource-cost alldifferent constraint ⋮ Weighted graphs with all Hamiltonian cycles of the same length ⋮ Monge properties, discrete convexity and applications ⋮ A comparison of lower bounds for the symmetric circulant traveling salesman problem ⋮ Classifying traveling salesman problems ⋮ The maximum travelling salesman problem on symmetric Demidenko matrices ⋮ Efficiently solvable special cases of bottleneck travelling salesman problems ⋮ Travelling salesman paths on Demidenko matrices ⋮ A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time ⋮ A variable block insertion heuristic for the blocking flowshop scheduling problem with total flowtime criterion ⋮ Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming ⋮ The travelling salesman and the PQ-tree ⋮ The traveling salesman problem: An overview of exact and approximate algorithms ⋮ Optimal arcs for the traveling salesman problem ⋮ Minimizing the number of workers in a paced mixed-model assembly line ⋮ The constant objective value property for multidimensional assignment problems ⋮ Monge and feasibility sequences in general flow problems ⋮ The \(x\)-and-\(y\)-axes travelling salesman problem ⋮ An asymmetric analogue of van der Veen conditions and the traveling salesman problem ⋮ Euclidean TSP on two polygons ⋮ SC-Hamiltonian graphs and digraphs: new necessary conditions and their impacts ⋮ The pyramidal capacitated vehicle routing problem ⋮ The traveling salesman problem: new polynomial approximation algorithms and domination analysis ⋮ Two-machine flow shop scheduling problems with no-wait jobs ⋮ The Northwest corner rule revisited ⋮ Recognising permuted Demidenko matrices ⋮ Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem ⋮ Hamiltonian path and symmetric travelling salesman polytopes ⋮ Two machine flow shop scheduling problem with no wait in process: Controllable machine speeds ⋮ Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood ⋮ The computational complexity of the \(k\)-minimum spanning tree problem in graded matrices ⋮ Pyramidal tours with step-backs and the asymmetric traveling salesman problem ⋮ Stability aspects of the traveling salesman problem based on \(k\)-best solutions ⋮ K-center and K-median problems in graded distances ⋮ Minimum-weight cycle covers and their approximability ⋮ Scheduling of flexible flow lines in an automobile assembly plant ⋮ Combinatorial optimization models for production scheduling in automated manufacturing systems ⋮ Three value TSP and linkages with the three value linear spanning 2-forests ⋮ Traveling salesman games with the Monge property ⋮ A two-machine no-wait flow shop problem with two competing agents ⋮ A heuristic for scheduling two-machine no-wait flow shops with anticipatory setups ⋮ Fast local search algorithms for the handicapped persons transportation problem ⋮ Linearity in the traveling salesman problem ⋮ Four-point conditions for the TSP: the complete complexity classification ⋮ Small and large TSP: Two polynomially solvable cases of the traveling salesman problem ⋮ Survey of facial results for the traveling salesman polytope ⋮ New exponential neighbourhood for polynomially solvable TSPs ⋮ Classes of matrices for the traveling salesman problem ⋮ An \(O(n)\) algorithm to solve the Bottleneck Traveling Salesman Problem restricted to ordered product matrices ⋮ An asymmetric analog of van der Veen conditions and the traveling salesman problem. II ⋮ Special cases of the traveling salesman problem ⋮ Pyramidal tours and the traveling salesman problem

This page was built for publication: