Solving a Random Asymmetric TSP Exactly in Quasi-Polynomial Time w.h.p

2023/08/05 by Tolson Bell, Alan Frieze, Bell, Tolson +1
#cs.DS #math.CO

paper · pdf · doi:10.48550/arxiv.2308.02946

Abstract

Let the costs C(i,j) for an instance of the Asymmetric Traveling Salesperson Problem (ATSP) be independent copies of a non-negative random variable C from a class of distributions that include the uniform [0,1] distribution and the exponential mean 1 distribution with mean 1. We describe an algorithm that solves ATSP exactly in time e^log^2+o(1)n, w.h.p.

Related

• Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap
• Approximation Algorithms for the Asymmetric Traveling Salesman Problem : Describing two recent methods
• A Randomized Rounding Algorithm for the Asymmetric Traveling Salesman Problem
• Improved Smoothed Analysis of 2-Opt for the Euclidean TSP
• Fast Exact Method for Solving the Travelling Salesman Problem