5 ms·
Ever heard of the traveling salesman problem because that is worse than linear, it is factorial. Granted, that is probably overkill for most people and my team
by mrep 4y ago
Ever heard of the traveling salesman problem because that is worse than linear, it is factorial. Granted, that is probably overkill for most people and my team (Not FedEx) just does NxN so it is only quadratic but it is definitely not constant nor even linear.
- whatever1 4y agoExactly because tsp variants are exponentially combinatorial we solve them with a strict time limit and use the best found solution. So for practical applications they are constant time.
- appletrotter 4y ago> So for practical applications they are constant time. So they should be able to handle all of this on a raspberry pi, if the size of the input has no effect on processing time.
- whatever1 4y agoYep a raspberry pi can give you A solution. It is not difficult to find a solution to routing problems, the difficult part is to get probably near optimal solution (<1% optimality gap).
- appletrotter 4y agoSo it scales with optimality but not size?
- whatever1 4y agoIt scales with the number of feasible routes for the particular problem instance you are looking at. The issue is that there are exponentially many of them and you cannot easily rule out that there is no better solution than the one you have on hand. That is why we solve these problems for as long as possible with as many resources as possible.