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.
https://arxiv.org/pdf/1708.04215.pdf
Regards,
Joe
Assymetric traveling salesman problem
Moderator: Joseph Malkevitch

 Posts: 1308
 Joined: Tue Aug 28, 2007 2:52 pm
 Location: Jamaica, New York
 Contact:
Assymetric traveling salesman problem
Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451
email:
malkevitch@york.cuny.edu
web page:
http://york.cuny.edu/~malk
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451
email:
malkevitch@york.cuny.edu
web page:
http://york.cuny.edu/~malk
Return to “Math is More: General Discussion”
Who is online
Users browsing this forum: No registered users and 1 guest