Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem
From MaRDI portal
Publication:1119486
DOI10.1016/0377-2217(89)90470-0zbMath0671.90085MaRDI QIDQ1119486
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
traveling salesman; heuristic algorithm; triangle inequality; performance bounds; transformation of the distance matrix
90C35: Programming involving graphs or networks
65K05: Numerical mathematical programming methods
90C06: Large-scale problems in mathematical programming
90C10: Integer programming
Related Items
A note on dual solutions of the assignment problem in connection with the traveling salesman problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On dual solutions of the linear assignment problem
- Transforming asymmetric into symmetric traveling salesman problems
- On the relationship of approximation algorithms for the minimum and the maximum traveling salesman problem
- Identification of non-optimal arcs for the traveling salesman problem
- A Dynamic Programming Approach to Sequencing Problems
- On the refinement of bounds of heuristic algorithms for the traveling salesman problem
- Improving Christofides' lower bound for the traveling salesman problem
- Sharp bounds for Karp's “patching”-algorithm for the approximate solution of the traveling salesman problem
- Ein beitrag zur klassifizierung von rundreiseproblemen
- Technical Note—Data-Dependent Bounds for Heuristics to Find a Minimum Weight Hamiltonian Circuit
- On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
- Some Examples of Difficult Traveling Salesman Problems
- Travelling Salesman and Assignment Problems: A Survey
- Approximative Algorithms for Discrete Optimization Problems
- An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
- Zu verschärfungen der christofibes-schranke fü den wert einer optimalen tour des enndrelseproblems
- Technical Note—Bounds for the Travelling-Salesman Problem
