Could someone tell me how many stopping points are needed for the traveling salesman to be impractical to be solved by current computing?

  • 2
    $\begingroup$ "The current TSP state-of-the-art exact solver, Concorde, remains unbeaten. Concorde has been used to optimally solve instances of several thousand cities and, for fewer than 1 000 cities, does so in very feasible running times." source $\endgroup$ Jun 28 '21 at 22:30
  • $\begingroup$ Strictly speaking, the hardness of a TSP instance is not measured by the number of cities. Small instances can be considerably more difficult than huge instances. The same is true for any NP-hard problem. Further, an instance can be rather easy for algorithm A but a lot harder for algorithm B. The opposite can be true for some other instance. $\endgroup$
    – Juho
    Jun 29 '21 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.