On the worst-case performance of some algorithms for the asymmetric traveling salesman problem

DOI10.1002/net.3230120103zbMath0478.90070WikidataQ57401646 ScholiaQ57401646MaRDI QIDQ3936521

Giulia Galbiati, Francesco Maffioli, Alan M. Frieze

Publication date: 1982

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230120103

zbMATH Keywords

worst-case performance; asymmetric traveling salesman problem; comparison of heuristic algorithms; n city problem

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

65K05: Numerical mathematical programming methods

Related Items

Minimum-weight two-connected spanning networks, Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems, Towards auction algorithms for large dense assignment problems, LP-based solution methods for the asymmetric TSP, An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality, On the relationship between ATSP and the cycle cover problem, Approximately fair cost allocation in metric traveling salesman games, The on-line asymmetric traveling salesman problem, On the relationship of approximation algorithms for the minimum and the maximum traveling salesman problem, Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem, A worst-case analysis of two approximate algorithms for the asymmetric travelling salesman problem, Analysis of the Held-Karp lower bound for the asymmetric TSP, An approximation algorithm for the asymmetric travelling salesman problem with distances one and two, A \(2_3^2\) superstring approximation algorithm, A bound for the symmetric travelling salesman problem through matroid formulation, A note on the approximation of the asymmetric traveling salesman problem., Complexity of the directed spanning cactus problem, Heuristic methods and applications: A categorized survey, Traveling salesman path problems, Asymmetry in \(k\)-center variants, The Directed Minimum Latency Problem, A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem, Sharp bounds for Karp's “patching”-algorithm for the approximate solution of the traveling salesman problem

Cites Work

• An extension of Christofides heuristic to the k-person travelling salesman problem
• An Analysis of the Greedy Heuristic for Independence Systems
• Computer Solutions of the Traveling Salesman Problem
• Unnamed Item