Does the TSP (traveling salesman problem) change in difficulty when the number of dimensions is greater than...
up vote
1
down vote
favorite
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?
graph-theory algorithms
asked Dec 1 at 19:59
chase
1326
add a comment |
up vote
1
down vote
favorite
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?
graph-theory algorithms
asked Dec 1 at 19:59
chase
1326
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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?
graph-theory algorithms
asked Dec 1 at 19:59
chase
1326
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?
graph-theory algorithms
graph-theory algorithms
asked Dec 1 at 19:59
chase
1326
asked Dec 1 at 19:59
chase
1326
asked Dec 1 at 19:59
chase
1326
asked Dec 1 at 19:59
chase
1326
asked Dec 1 at 19:59
chase
1326
1326
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
4
down vote
accepted
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.
answered Dec 1 at 20:13
Jeffery
834
2
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.
– Ian
Dec 1 at 20:45
1
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.
– Misha Lavrov
Dec 1 at 22:29
1
Except of course for $d=1$: If the cities are points of $Bbb R$ with the euclidean distance then the TSP is pretty easy...
– David C. Ullrich
Dec 2 at 18:49
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
accepted
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.
answered Dec 1 at 20:13
Jeffery
834
2
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.
– Ian
Dec 1 at 20:45
1
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.
– Misha Lavrov
Dec 1 at 22:29
1
Except of course for $d=1$: If the cities are points of $Bbb R$ with the euclidean distance then the TSP is pretty easy...
– David C. Ullrich
Dec 2 at 18:49
add a comment |
up vote
4
down vote
accepted
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.
answered Dec 1 at 20:13
Jeffery
834
2
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.
– Ian
Dec 1 at 20:45
1
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.
– Misha Lavrov
Dec 1 at 22:29
1
Except of course for $d=1$: If the cities are points of $Bbb R$ with the euclidean distance then the TSP is pretty easy...
– David C. Ullrich
Dec 2 at 18:49
add a comment |
up vote
4
down vote
accepted
up vote
4
down vote
accepted
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.
answered Dec 1 at 20:13
Jeffery
834
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.
answered Dec 1 at 20:13
Jeffery
834
answered Dec 1 at 20:13
Jeffery
834
answered Dec 1 at 20:13
Jeffery
834
answered Dec 1 at 20:13
Jeffery
834
834
2
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.
– Ian
Dec 1 at 20:45
1
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.
– Misha Lavrov
Dec 1 at 22:29
1
Except of course for $d=1$: If the cities are points of $Bbb R$ with the euclidean distance then the TSP is pretty easy...
– David C. Ullrich
Dec 2 at 18:49
add a comment |
2
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.
– Ian
Dec 1 at 20:45
1
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.
– Misha Lavrov
Dec 1 at 22:29
1
Except of course for $d=1$: If the cities are points of $Bbb R$ with the euclidean distance then the TSP is pretty easy...
– David C. Ullrich
Dec 2 at 18:49
2
2
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.
– Ian
Dec 1 at 20:45
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.
– Ian
Dec 1 at 20:45
1
1
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.
– Misha Lavrov
Dec 1 at 22:29
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.
– Misha Lavrov
Dec 1 at 22:29
1
1
Except of course for $d=1$: If the cities are points of $Bbb R$ with the euclidean distance then the TSP is pretty easy...
– David C. Ullrich
Dec 2 at 18:49
Except of course for $d=1$: If the cities are points of $Bbb R$ with the euclidean distance then the TSP is pretty easy...
– David C. Ullrich
Dec 2 at 18:49
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3021753%2fdoes-the-tsp-traveling-salesman-problem-change-in-difficulty-when-the-number-o%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
