Re:Svante Pääbo awarded Nobel Prize for studies of extinct h...
by dave18 on Tuesday October 04, 2022 @03:49AM
(#33077576)
No. Theory offers you a quadratic speed-up of the exponential worst-case running time. And this is the theory. In practice, it looks worse.
....and: exponential worst-case running time is almost never observed in any kind of practical NP-hard optimization problem when using state-of-the-art algorithms on digital computers...
and talking about the Steiner tree problem: It is basically solved for all practical matters. Same for the famous travelling salesman problem. Look at this solver: https://www.math.uwaterloo.ca/tsp/concorde.html
Or look at these amazing results: https://www.math.uwaterloo.ca/tsp/star/index.html