Assymetric traveling salesman problem

A place to have an open discussion about Math is More

Moderator: Joseph Malkevitch

Joseph Malkevitch
Posts: 1222
Joined: Tue Aug 28, 2007 2:52 pm
Location: Jamaica, New York

Assymetric traveling salesman problem

Postby Joseph Malkevitch » Fri Oct 06, 2017 4:13 pm

Dear Colleagues,

The TSP (traveling salesman problem) asks for a simple closed tour (hamiltoniian circuit) through a weighted graph (triangle inequality holds) which visits each vertex of the graph once and only once with minimum cost. In some "contexts" the distance from A to B is not the same as from B to A, so the asymmetric TSP asks for a tour of a strongly connected digraph (routes from any X to any Y and back for all pairs X and Y) which has minimum cost. Finding the minimum answer is computational hard but recently a breakthrough has been made in finding "good" approximations in the asymmetric case. The constants involved in the analysis are very large but from a theory point of view the new result is remarkable.


Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451


web page:

Return to “Math is More: General Discussion”

Who is online

Users browsing this forum: No registered users and 1 guest