alt Hacker NewsIt must be equivalent to the knapsack problem, for which many faster close-to-optimal algorithms exist. Am I missing something?
It must be equivalent to the knapsack problem, for which many faster close-to-optimal algorithms exist. Am I missing something?
It’s not equivalent. Knapsack is weakly NP-hard, while optimal join order is strongly NP-hard. Also, algorithms that only approximate an optimal solution don’t generally carry over between NP-hard problems, unless they are structurally very similar.