The Traveling-Salesman Problem and Minimum Spanning Trees

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

Michael Held, Richard M. Karp

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

Programming involving graphs or networks (90C35) Applications of mathematical programming (90C90) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Combinatorial optimization (90C27)

Related Items (only showing first 100 items - show all)

Improving Christofides' lower bound for the traveling salesman problem ⋮ Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ Global strategies for augmenting the efficiency of TSP heuristics ⋮ Random Instances of Problems in NP – Algorithms and Statistical Physics ⋮ A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives ⋮ Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps ⋮ A direct dual method for the mixed plant location problem with some side constraints ⋮ Integer Programming Formulations for Minimum Spanning Tree Interdiction ⋮ The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem ⋮ The traveling-salesman problem and minimum spanning trees: Part II ⋮ An effective approach for optimization of a perishable inventory system with uncertainty in both demand and supply ⋮ A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP ⋮ A deterministic better-than-3/2 approximation algorithm for metric TSP ⋮ Configuration‐based approach for topological problems in the design of wireless sensor networks ⋮ Formulations and a Lagrangian relaxation approach for the prize collecting traveling salesman problem ⋮ Hamiltonian circuits with generalised cost ⋮ A reinforced hybrid genetic algorithm for the traveling salesman problem ⋮ Polyhedral techniques in combinatorial optimization: matchings and tours ⋮ Refinement of Lagrangian bounds in optimization problems ⋮ The Minimum Spanning Tree Problem with Time Window Constraints ⋮ Incorporating Aggregate Diversity in Recommender Systems Using Scalable Optimization Approaches ⋮ An efficient mixed integer linear programming model for the minimum spanning tree problem ⋮ Quantum complexity for vector domination problem ⋮ A RELAX-AND-CUT ALGORITHM FOR THE KNAPSACK NODE WEIGHTED STEINER TREE PROBLEM ⋮ Unnamed Item ⋮ Hidden Hamiltonian Cycle Recovery via Linear Programming ⋮ Graphical-structure-based models for routing problems ⋮ A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem ⋮ The travelling salesman problem and a class of polyhedra of diameter two ⋮ New Approximation Algorithms for (1,2)-TSP ⋮ Separating maximally violated comb inequalities in planar graphs ⋮ A Lagrangian-Based Algorithm for a Combinatorial Motion Planning Problem ⋮ A New Formulation for the Travelling Salesman Problem ⋮ A modified subgradient algorithm for Lagrangean relaxation ⋮ Construction heuristics for the asymmetric TSP. ⋮ Lineare Charakterisierungen von Travelling Salesman Problemen ⋮ A general scheme for automatic generation of search heuristics from specification \(dependencies^{*}\) ⋮ Some relationships between lagrangian and surrogate duality in integer programming ⋮ Quantity discount decisions under conditions of multiple items, multiple suppliers and resource limitations ⋮ The traveling salesman problem: A duality approach ⋮ The Held—Karp algorithm and degree-constrained minimum 1-trees ⋮ Affinity propagation and uncapacitated facility location problems ⋮ Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem ⋮ On the existence of duality gaps for mixed integer programming ⋮ An Improved Analysis of the Mömke--Svensson Algorithm for Graph-TSP on Subquartic Graphs ⋮ Modeling and Managing Uncertainty in Process Planning and Scheduling ⋮ Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations ⋮ A restricted Lagrangean approach to the traveling salesman problem ⋮ Lagrangean Relaxation-Based Techniques for Solving Facility Location Problems ⋮ Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut ⋮ Unnamed Item ⋮ On the refinement of bounds of heuristic algorithms for the traveling salesman problem ⋮ Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality ⋮ Solving the Watchman Route Problem with Heuristic Search ⋮ Validation of subgradient optimization ⋮ On recursive computation of minimum spanning trees for special partial graphs ⋮ Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem ⋮ The 2-quasi-greedy algorithm for cardinality constrained matroid bases ⋮ Polyhedral proof methods in combinatorial optimization ⋮ The asymmetric m-travelling salesman problem: A duality based branch-and- bound algorithm ⋮ Efficient algorithms for the capacitated concentrator location problem ⋮ A computational evaluation of two subgradient search methods ⋮ On a mixture of the fix-and-relax coordination and Lagrangian substitution schemes for multistage stochastic mixed integer programming ⋮ Duality for mixed-integer convex minimization ⋮ Computing assortative mixing by degree with the \(s\)-metric in networks using linear programming ⋮ A linear-time algorithm for finding a minimum spanning pseudoforest ⋮ Evolutionary algorithms and matroid optimization problems ⋮ Lower bounding procedure for the asymmetric quadratic traveling salesman problem ⋮ A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem ⋮ A hybrid Lagrangean heuristic with GRASP and path-relinking for set \(k\)-covering ⋮ Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation ⋮ Dual formulations and subgradient optimization strategies for linear programming relaxations of mixed-integer programs ⋮ A matroid algorithm and its application to the efficient solution of two optimization problems on graphs ⋮ Large traveling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation ⋮ A hybrid approach of bundle and Benders applied large mixed linear integer problem ⋮ A Lagrangean approach to the degree-constrained minimum spanning tree problem ⋮ Lagrangian dual ascent by generalized linear programming ⋮ A lower bound for the breakpoint phylogeny problem ⋮ A simple LP relaxation for the asymmetric traveling salesman problem ⋮ Lagrangian heuristic for a class of the generalized assignment problems ⋮ The combinatorial bandwidth packing problem ⋮ Some aspects of integer programming duality ⋮ On the choice of step size in subgradient optimization ⋮ Lower and upper bounds for the \(m\)-peripatetic vehicle routing problem ⋮ Heuristics and their design: A survey ⋮ Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry ⋮ An exact algorithm for the Boolean connectivity problem for \(k\)-CNF ⋮ An exact algorithm to minimize the makespan in project scheduling with scarce resources and generalized precedence relations ⋮ A dual ascent algorithm for the 1-tree relaxation of the symmetric traveling salesman problem ⋮ A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation ⋮ Exact hybrid algorithms for solving a bi-objective vehicle routing problem ⋮ Analyzing the Held-Karp TSP bound: A monotonicity property with application ⋮ A comparison of lower bounds for the symmetric circulant traveling salesman problem ⋮ Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem ⋮ The capacitated maximal covering location problem with backup service ⋮ Minimal spanning trees and partial sorting ⋮ A heuristic decomposition approach to optimal control in a water supply model ⋮ Nonlinear resolving functions for the travelling salesman problem ⋮ Spanning closed walks and TSP in 3-connected planar graphs ⋮ The symmetric traveling salesman problem and edge exchanges in minimal 1- trees

This page was built for publication: The Traveling-Salesman Problem and Minimum Spanning Trees