Timeline for Solving time of large TSP instances
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 11, 2022 at 19:58 | answer | added | Ordoshsen | timeline score: 2 | |
| Jan 10, 2022 at 0:12 | answer | added | D.W.♦ | timeline score: 1 | |
| Jan 9, 2022 at 14:53 | comment | added | Yuval Filmus | You’ll have to take a look at the actual heuristic. Is just like SAT solvers, which don’t have to run in time $2^n$. | |
| Jan 9, 2022 at 14:35 | comment | added | Nepomuk Hirsch | But how does a heuristic knows that it found an optimal solution without an exhaustive search? Neither any metsheuristic nor a specialized heuristic such as Christofides can know this. Via B&B you can track the gap but this is still exponential (but potentially less than 2^n for practical instances). | |
| Jan 9, 2022 at 14:28 | comment | added | Yuval Filmus | It is an optimal solution, and you are wrong that you have to check all possible tours. These heuristics work differently, and perform much better in practice. Their worst case complexity is unclear, but mostly irrelevant. | |
| Jan 9, 2022 at 14:22 | comment | added | Nepomuk Hirsch | I agree but they claim that it is an optimal solution and not a heuristical / non-optimal solution. Am I wrong that for for such an optimal solution all possible tours need to be checked? (I also agree that trivial instances might be solved more easily, but this a real world 85,900 cities instance, I doubt that it is being used as a benchmark if it could be solved trivially). | |
| Jan 9, 2022 at 14:01 | comment | added | Yuval Filmus | The optimization variant of TSP is NP-hard, hence, finding an optimal tour takes $2^n$ steps for $n$ cities. The obvious algorithm actually takes time proportional to $n!$, though this can be improved. Real-life algorithms use heuristics which run a lot faster in practice, especially on instance which are not worst-case. | |
| Jan 9, 2022 at 14:00 | history | edited | Yuval Filmus | CC BY-SA 4.0 |
added 4 characters in body
|
| Jan 9, 2022 at 13:34 | history | asked | Nepomuk Hirsch | CC BY-SA 4.0 |