Solving a Random Asymmetric TSP Exactly in Quasi‐Polynomial Time W.H.P.
Abstract
ABSTRACT Let the costs for an instance of the Asymmetric Traveling Salesperson Problem (ATSP) be independent copies of a nonnegative random variable from a class of distributions that include the uniform distribution and the exponential mean 1 distribution with mean 1. We describe an algorithm that solves ATSP exactly in time , w.h.p.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Vehicle Routing Optimization Methods
Advanced Graph Theory Research
Publication details
- Journal / source
- Random Structures and Algorithms
- Volume
- 68
- Issue
- 2
- Publication date
- 7 February 2026
- Language
- EN