New answers tagged traveling-salesman
0
votes
Reducing euclidean TSP of smaller size to euclidean TSP of bigger size
Here's an idea that doesn't work: Assume K = N-1. Take any node X and create another node X' at a distance epsilon from X, and calculate all the distances to X', then solve the N problem. If that ...
Top 50 recent answers are included
Related Tags
traveling-salesman × 242algorithms × 83
graphs × 57
optimization × 41
complexity-theory × 36
np-complete × 28
approximation × 28
np-hard × 24
heuristics × 19
graph-traversal × 14
np × 13
shortest-path × 12
reductions × 11
reference-request × 11
time-complexity × 8
genetic-algorithms × 8
dynamic-programming × 7
linear-programming × 7
integer-programming × 7
algorithm-analysis × 6
p-vs-np × 6
hamiltonian-path × 6
decision-problem × 5
weighted-graphs × 5
minimum-spanning-tree × 5