The Traveling-Salesman Problem and Minimum Spanning Trees

DOI10.1287/opre.18.6.1138zbMath0226.90047WikidataQ55899753 ScholiaQ55899753MaRDI QIDQ5633847

Richard M. Karp, Michael Held

Publication date: 1970

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

Full work available at URL: https://doi.org/10.1287/opre.18.6.1138

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C90: Applications of mathematical programming

90C08: Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)

90C27: Combinatorial optimization

Related Items

Validation of subgradient optimization, Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem, On the existence of duality gaps for mixed integer programming, The traveling-salesman problem and minimum spanning trees: Part II, A modified subgradient algorithm for Lagrangean relaxation, Construction heuristics for the asymmetric TSP., A general scheme for automatic generation of search heuristics from specification \(dependencies^{*}\), A note on the prize collecting traveling salesman problem, Survivable networks, linear programming relaxations and the parsimonious property, Capacitated emergency facility siting with multiple levels of backup, Match twice and stitch: a new TSP tour construction heuristic., Solving the combinatorial double auction problem, Some aspects of integer programming duality, On the choice of step size in subgradient optimization, Heuristics and their design: A survey, The hierarchical network design problem with transshipment facilities, Travelling salesman problem tools for microcomputers, How to find Steiner minimal trees in Euclidean \(d\)-space, The traveling salesman problem: An overview of exact and approximate algorithms, Configuration of fully replicated distributed database system over wide area networks, Locating concentrators in centralized computer networks, An in-depth empirical investigation of non-greedy approaches for the minimum spanning tree problem, Paroids: A canonical format for combinatorial optimization, Analysis of the Held-Karp lower bound for the asymmetric TSP, On the solving strategy in composite heuristics, The multicovering problem, A decomposition technique for mixed integer programming problems, A language and a program for stating and solving combinatorial problems, The seriation problem and the travelling salesman problem, A survey of various tactics for generating Lagrangian multipliers in the context of Lagrangian duality, Optimizing tabu list size for the traveling salesman problem, Plant location with minimum inventory, Estimating the Held-Karp lower bound for the geometric TSP, Minimum directed 1-subtree relaxation for score orienteering problem, Algorithms for a multi-level network optimization problem, A technique for speeding up the solution of the Lagrangean dual, Analyzing tradeoffs between zonal constraints and accessibility in facility location, A fast optimization method based on a hierarchical strategy for the travelling salesman problem, On spanning tree problems with multiple objectives, A quadratic integer programming method for minimizing the mean squared deviation of completion times, On some difficult linear programs coming from set partitioning, Solving the anti-covering location problem using Lagrangian relaxation, Upper and lower bounds for the single source capacitated location problem., Parallel machine scheduling with earliness--tardiness penalties and additional resource con\-straints., The multidimensional 0-1 knapsack problem: an overview., An effective implementation of the Lin-Kernighan traveling salesman heuristic, A new variant of a vehicle routing problem: Lower and upper bounds, Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems, Relaxed tours and path ejections for the traveling salesman problem, Multiple bottleneck assignment problem, Stronger \(K\)-tree relaxations for the vehicle routing problem, Solving the shortest route cut and fill problem using simulated annealing, The cardinality constrained covering traveling salesman problem, Steps toward accurate reconstructions of phylogenies from gene-order data., Lagrangean relaxation. (With comments and rejoinder)., An exact algorithm for the capacitated shortest spanning arborescence, Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies, Genetic algorithms for the traveling salesman problem, Designing and reporting on computational experiments with heuristic methods, Further results on the probabilistic traveling salesman problem, The selection and scheduling of telecommunication calls with time windows, Implementation analysis of efficient heuristic algorithms for the traveling salesman problem, Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition, A hybrid genetic-GRASP algorithm using Lagrangean relaxation for the traveling salesman problem, FINITE SIZE SCALING AND CRITICAL TRANSITION IN CONSTRAINED TRAVELING SALESMAN PROBLEM, A direct dual method for the mixed plant location problem with some side constraints, Some relationships between lagrangian and surrogate duality in integer programming, Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations, A restricted Lagrangean approach to the traveling salesman problem, The travelling salesman problem and a class of polyhedra of diameter two, Lineare Charakterisierungen von Travelling Salesman Problemen, The traveling salesman problem: A duality approach, The Held—Karp algorithm and degree-constrained minimum 1-trees