HackerTrans
TopNewTrendsCommentsPastAskShowJobs

dave18

no profile record

comments

dave18
·4 ปีที่แล้ว·discuss
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
dave18
·4 ปีที่แล้ว·discuss
Sorry, but this was a somewhat bad advise. You can solve huge Steiner tree problems (up to a million of edges) in practice to optimality. See for example this solver: https://scipjack.zib.de/

There is a wide-spread misconception of the meaning of NP-complete, unfortunately. Also, it should probably be NP-hard, not NP-complete, the latter is for a decision problem only.