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 ⋮ Steps toward accurate reconstructions of phylogenies from gene-order data. ⋮ A new heuristic algorithm for laser antimissile strategy optimization ⋮ A Lagrangean decomposition for the maximum independent set problem applied to map labeling ⋮ Lagrangean relaxation. (With comments and rejoinder). ⋮ A fast optimization method based on a hierarchical strategy for the travelling salesman problem ⋮ Further results on the probabilistic traveling salesman problem ⋮ On spanning tree problems with multiple objectives ⋮ A quadratic integer programming method for minimizing the mean squared deviation of completion times ⋮ Distribution network design for fixed lifetime perishable products: a model and solution approach ⋮ On some difficult linear programs coming from set partitioning ⋮ 2-change for k-connected networks ⋮ Hybrid approaches for the two-scenario max-min knapsack problem ⋮ Better s-t-Tours by Gao Trees ⋮ Improved Approximations for Cubic Bipartite and Cubic TSP ⋮ Weighted amplifiers and inapproximability results for travelling salesman problem ⋮ Approximation algorithms for the directed \(k\)-Tour and \(k\)-Stroll problems ⋮ A Lagrangian relaxation algorithm for optimizing a bi-objective agro-supply chain model considering CO\(_2\) emissions ⋮ An exact algorithm for the capacitated shortest spanning arborescence ⋮ The symmetric travelling salesman problem. I: New fast lower bounds for the problem of optimal 2-matching ⋮ Efficient optimization of the Held-Karp lower bound ⋮ The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems ⋮ Solving the anti-covering location problem using Lagrangian relaxation ⋮ Solving large-scale TSP using a fast wedging insertion partitioning approach ⋮ Improving the robustness of EPS to solve the TSP ⋮ Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies ⋮ Genetic algorithms for the traveling salesman problem ⋮ Multi-period stochastic programming models for two-tiered emergency medical service system ⋮ An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem ⋮ Designing and reporting on computational experiments with heuristic methods ⋮ The Lagrangian relaxation for the combinatorial integral approximation problem ⋮ On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms ⋮ Subtour elimination constraints imply a matrix-tree theorem SDP constraint for the TSP ⋮ Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems ⋮ Approximation algorithms for constructing spanning \(K\)-trees using stock pieces of bounded length ⋮ On the computational efficiency of subgradient methods: a case study with Lagrangian bounds ⋮ Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm ⋮ Upper and lower bounds for the single source capacitated location problem. ⋮ A stabilized column generation scheme for the traveling salesman subtour problem ⋮ Parallel machine scheduling with earliness--tardiness penalties and additional resource con\-straints. ⋮ The symmetric travelling salesman problem. II: New low bounds ⋮ A discrete cross aisle design model for order-picking warehouses ⋮ The multidimensional 0-1 knapsack problem: an overview. ⋮ Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem

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