Publication:3768703

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

Publication date: 1985

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

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

05C35: Extremal problems in graph theory

90-02: Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming

Related Items

An asymmetric analogue of van der Veen conditions and the traveling salesman problem, Pyramidal tours and multiple objectives, Monge and feasibility sequences in general flow problems, SC-Hamiltonian graphs and digraphs: new necessary conditions and their impacts, Classes of matrices for the traveling salesman problem, Pyramidal tours and the traveling salesman problem, Different behaviour of a double branch-and-bound algorithm on \(\mathrm {Fm}|\mathrm{prmu}|C_{\max}\) and \(\mathrm {Fm}|\mathrm {block}|C_{\max}\) problems, A new asymmetric pyramidally solvable class of the traveling salesman problem, Classifying traveling salesman problems, Minimum-weight cycle covers and their approximability, A polynomial-time solution to Papadimitriou and Steiglitz's ``traps, An algorithm for the detection and construction of Monge sequences, Efficiently solvable special cases of bottleneck travelling salesman problems, A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time, The traveling salesman problem: An overview of exact and approximate algorithms, Optimal arcs for the traveling salesman problem, 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, Scheduling of flexible flow lines in an automobile assembly plant, Combinatorial optimization models for production scheduling in automated manufacturing systems, Small and large TSP: Two polynomially solvable cases of the traveling salesman problem, An \(O(n)\) algorithm to solve the Bottleneck Traveling Salesman Problem restricted to ordered product matrices, Special cases of the traveling salesman problem, Graphs in which all Hamiltonian cycles have the same length, The Convex-hull-and-k-line Travelling Salesman Problem, Efficiently solvable special cases of hard combinatorial optimization problems, 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, Weighted graphs with all Hamiltonian cycles of the same length, A heuristic for scheduling two-machine no-wait flow shops with anticipatory setups, Linearity in the traveling salesman problem, Survey of facial results for the traveling salesman polytope, An asymmetric analog of van der Veen conditions and the traveling salesman problem. II, Two-machine flow shop scheduling problems with no-wait jobs, 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, Traveling salesman games with the Monge property, Monge matrices make maximization manageable, On the recognition of permuted bottleneck Monge matrices, Perspectives of Monge properties in optimization, The maximum travelling salesman problem on symmetric Demidenko matrices, Euclidean TSP on two polygons, The pyramidal capacitated vehicle routing problem, Multiobjective traveling salesperson problem on Halin graphs, Some local search algorithms for no-wait flow-shop problem with makespan criterion, On the Euclidean TSP with a permuted van der Veen matrix, Monge properties, discrete convexity and applications, Fast local search algorithms for the handicapped persons transportation problem, The traveling salesman problem: new polynomial approximation algorithms and domination analysis, New exponential neighbourhood for polynomially solvable TSPs