PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
February 9, 2026Random Structures and Algorithms0 citationsOpen Access

Solving a Random Asymmetric TSP Exactly in Quasi‐Polynomial Time W.H.P.

View Full Paper
TBTolson BellAFA. M. Frieze

Key Points

  • The research aims to present an efficient algorithm that solves the Asymmetric Traveling Salesperson Problem (ATSP) exactly.
  • Developed an algorithm targeting the ATSP
  • Utilized random variables from various distributions
  • Analyzed performance in quasi-polynomial time
  • Algorithm solves the ATSP exactly with high probability
  • Demonstrates efficiency over traditional methods by reducing computation time

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.

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Bell et al. (2026) studied this question.

synapsesocial.com/papers/69897a86f0ec2af6756e8b08https://doi.org/10.1002/rsa.70052
Ask AI
Helpful
Bookmark
Share
View Full Paper