1
$\begingroup$

The title pretty much says it all.

I am curious if the TSP is dependent only upon the number of cities, $c$, involved, or if the dimensionality, $d$, matters to the problem.

For example, if $d>>c$ does the problem shift in some manner, making the time to solve the problem less dependent on the number of cities?

$\endgroup$

1 Answer 1

4
$\begingroup$

The traveling salesman problem is, in its basic form, a graph theory problem. All vertices (the cities to visit) are connected, and all edges are assigned a "distance", and you need to answer: "what is the shortest route that starts at a given vertex, visits all other vertices, and comes back to the start point?"

The only thing that changes in a multi-dimensional format is that calculating these distances takes more variables, but this is calculated in linear time (I'm assuming Euclidean distances). But once you get calculate them all and get the graph described above, the problem is exactly the same. So no change in complexity.

$\endgroup$
3
  • 2
    $\begingroup$ Graph theory does have a notion of dimensionality to it, in that a graph may or may not be embeddable into $\mathbb{R}^n$ for certain $n$ (where "embedabble" means it can be drawn without intersecting edges). The smallest $n$ for which this can be done can be interpreted as the dimension of the graph itself. This dimensionality enters into certain problems (for example, coloring problems). It doesn't really enter into the TSP in any significant way, however. $\endgroup$
    – Ian
    Dec 1, 2018 at 20:45
  • 1
    $\begingroup$ What does affect TSP is whether the edge costs are metric: whether they satisfy the triangle inequality $d(u,w) \le d(u,v) + d(v,w)$. If the graph is embeddable in $\mathbb R^n$ for any $n$, then the edge costs (Euclidean distances) are metric, which allows for some approximation algorithms that do not work in general. $\endgroup$ Dec 1, 2018 at 22:29
  • 1
    $\begingroup$ Except of course for $d=1$: If the cities are points of $\Bbb R$ with the euclidean distance then the TSP is pretty easy... $\endgroup$ Dec 2, 2018 at 18:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .