Mathematics desk
< October 19	<< Sep \| October \| Nov >>	October 21 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 20[edit]

Traveling salesman problem, (tsp)[edit]

If the graph for the tsp obeys the triangle inequality, is that a special case that has been studied? Does it make it an easier problem?Rich (talk) 03:43, 20 October 2018 (UTC)[reply]

The Christofides algorithm works on graphs which obey the triangle inequality. CodeTalker (talk) 05:10, 20 October 2018 (UTC)[reply]

Apparently, this variant is known as Metric TSP, so you may find relevant information in that section.

I don't think it matters much, though. Any TSP problem which is not metric, can be reduced to a metric one; by replacing each TE-defying edge with the minimal distance allowed by TE. AFAIK the problem statement does not prohibit visiting the same city twice, so you can always go through other cities while traveling from A to B if it shortens your path, so the problems are equivalent.

Concretely, there are two kinds of reductions that are possible when given an arbitrary TSP graph:

Expand the graph into a full one, where the distance on each edge is the shortest path possible using the original graph.
Prune the graph, by removing any edge that is worth than the shortest distance allowed using the other edges.

So basically, there are only two kinds of "processed" TSP graphs, and it only makes sense to develop algorithms that work on one or the other, and reduce any arbitrary problem to one of them (the one that admits a better algorithm). -- Meni Rosenfeld (talk) 15:07, 25 October 2018 (UTC)[reply]