New answers tagged traveling-salesman
0
It's at least as hard as the "Traveling Salesman" problem, that is NP complete: TSP asks whether a salesman can visit n towns while travelling a distance ≤ K. Take the special case of one worker, who can do n jobs in a day if and only he travels a distance ≤ K, then the question "can the single available worker do all jobs in one day" is equivalent to TSP. ...
1
As it is mentioned in this paper, you can find a concave-hull of points in a 2-dimensional plate in $O(n \log n)$ (as complex as finding a convex hull).
Top 50 recent answers are included
Related Tags
traveling-salesman × 171algorithms × 60
graphs × 37
optimization × 32
complexity-theory × 28
np-complete × 20
approximation × 19
heuristics × 19
np-hard × 14
reference-request × 9
graph-traversal × 8
shortest-path × 7
np × 7
time-complexity × 6
reductions × 6
dynamic-programming × 6
integer-programming × 6
linear-programming × 5
weighted-graphs × 5
genetic-algorithms × 5
hamiltonian-path × 5
decision-problem × 4
minimum-spanning-tree × 4
algorithm-analysis × 3
p-vs-np × 3