An improved assignment lower bound for the Euclidean traveling salesman problem

DOI10.1016/0167-6377(85)90032-XzbMATH Open0565.90077MaRDI QIDQ1058993FDOQ1058993

Authors: William R. jun. Stewart 

Publication date: 1985

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

Recommendations

• Better assignment lower bounds for the Euclidean traveling salesman problem
• Improving Christofides' lower bound for the traveling salesman problem
• Publication:4733695
• A note on dual solutions of the assignment problem in connection with the traveling salesman problem
• On the refinement of bounds of heuristic algorithms for the traveling salesman problem

zbMATH Keywords

lower boundflow algorithmsEuclidean traveling salesmanimproved heuristicstransformation of the distance matrix

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Extremal problems in graph theory (05C35) Integer programming (90C10)

Cites Work

• The traveling-salesman problem
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• A man-machine approach toward solving the traveling salesman problem
• Title not available (Why is that?)
• Technical Note—Rounding Symmetric Traveling Salesman Problems with an Asymmetric Assignment Problem

Cited In (9)

• On the refinement of bounds of heuristic algorithms for the traveling salesman problem
• Title not available (Why is that?)
• Continuous reformulations and heuristics for the Euclidean travelling salesperson problem
• Title not available (Why is that?)
• Improving Christofides' lower bound for the traveling salesman problem
• A new lower bound for the geometric traveling salesman problem in terms of discrepancy
• A Fast Lower Bound for the Minimum Cost Perfect 2-Matching Linear Program
• Better assignment lower bounds for the Euclidean traveling salesman problem
• The symmetric travelling salesman problem. I: New fast lower bounds for the problem of optimal 2-matching

This page was built for publication: An improved assignment lower bound for the Euclidean traveling salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1058993)