Estimating the Held-Karp lower bound for the geometric TSP

DOI10.1016/S0377-2217(96)00214-7zbMath0948.90034OpenAlexW2020993691MaRDI QIDQ1291588

Antonia J. Jones, Christine L. Valenzuela

Publication date: 21 November 2000

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0377-2217(96)00214-7

zbMATH Keywords

Lagrangian relaxationtravelling salesmansubgradient optimizationHeld-Karp lower boundminimum 1-tree

Mathematics Subject Classification ID

Traffic problems in operations research (90B20) Methods of reduced gradient type (90C52)

Related Items

Method of scaling in approximate solution of the traveling salesman problem, Efficient optimization of the Held-Karp lower bound, Route efficiency implications of time windows and vehicle capacities in first- and last-mile logistics, Exact hybrid algorithms for solving a bi-objective vehicle routing problem, A note on relatives to the Held and Karp 1-tree problem, Embedding learning capability in Lagrangean relaxation: an application to the travelling salesman problem, New Bounds for the Traveling Salesman Constant, Fairness in ambulance routing for post disaster management, Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems, The cardinality constrained covering traveling salesman problem

Uses Software

• TSPLIB

Cites Work

• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
• The traveling salesman. Computational solutions for RSP applications
• Probabilistic Analysis of the Held and Karp Lower Bound for the Euclidean Traveling Salesman Problem
• Heuristic analysis, linear programming and branch and bound
• Multidimensional binary search trees used for associative searching
• Validation of subgradient optimization
• Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem
• The Traveling-Salesman Problem and Minimum Spanning Trees
• Minimization of unsmooth functionals
• The traveling-salesman problem and minimum spanning trees: Part II
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item