Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem

DOI10.1016/0377-2217(89)90470-0MaRDI QIDQ1119486zbMATH OpenOpenAlexFDO

Authors Bernd Jeromin, Frank Koerner

Publication date 1989

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

Full work available at URL https://doi.org/10.1016/0377-2217(89)90470-0

zbMATH Keywords

heuristic algorithmperformance boundstransformation of the distance matrixtraveling salesmantriangle inequality

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Integer programming (90C10) Programming involving graphs or networks (90C35)

Review text

The authors discuss the transformation of the distance matrix in the traveling salesman problem in order to use a given heuristic algorithm. Some performance bounds are derived.

Cites work

• A Dynamic Programming Approach to Sequencing Problems
• An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
• Approximative Algorithms for Discrete Optimization Problems
• Ein beitrag zur klassifizierung von rundreiseproblemen
• scientific article; zbMATH DE number 3898613 (Why is no real title available?)
• scientific article; zbMATH DE number 3956838 (Why is no real title available?)
• scientific article; zbMATH DE number 4039668 (Why is no real title available?)
• scientific article; zbMATH DE number 3759929 (Why is no real title available?)
• Identification of non-optimal arcs for the traveling salesman problem
• Improving Christofides' lower bound for the traveling salesman problem
• On dual solutions of the linear assignment problem
• On the refinement of bounds of heuristic algorithms for the traveling salesman problem
• On the relationship of approximation algorithms for the minimum and the maximum traveling salesman problem
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• Sharp bounds for Karp's “patching”-algorithm for the approximate solution of the traveling salesman problem
• Some Examples of Difficult Traveling Salesman Problems
• Technical Note—Bounds for the Travelling-Salesman Problem
• Technical Note—Data-Dependent Bounds for Heuristics to Find a Minimum Weight Hamiltonian Circuit
• Transforming asymmetric into symmetric traveling salesman problems
• Travelling Salesman and Assignment Problems: A Survey
• Zu verschärfungen der christofibes-schranke fü den wert einer optimalen tour des enndrelseproblems

Cited in

(2)

• The Crown Inequalities for the Symmetric Traveling Salesman Polytope
• A note on dual solutions of the assignment problem in connection with the traveling salesman problem

This page was built for publication: Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem

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