Better assignment lower bounds for the Euclidean traveling salesman problem

DOI10.1080/02331938708843251zbMath0633.90088OpenAlexW1989292274MaRDI QIDQ3771999

A. Volgenant, Roy Jonker, Erik Van der Sluis

Publication date: 1987

Published in: Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/02331938708843251

zbMATH Keywords

Computational resultsflow algorithmsEuclidean Traveling Salesmanassignment lower bounds

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05) Integer programming (90C10)

Related Items

The symmetric travelling salesman problem. I: New fast lower bounds for the problem of optimal 2-matching

Cites Work

• On dual solutions of the linear assignment problem
• An improved assignment lower bound for the Euclidean traveling salesman problem
• An algorithm for the traveling salesman problem with pickup and delivery customers
• Nonoptimal Edges for the Symmetric Traveling Salesman Problem
• Improving Christofides' lower bound for the traveling salesman problem
• Technical Note—Rounding Symmetric Traveling Salesman Problems with an Asymmetric Assignment Problem
• A restricted Lagrangean approach to the traveling salesman problem
• Technical Note—Bounds for the Travelling-Salesman Problem