3 ms·
It must be equivalent to the knapsack problem, for which many faster close-to-optimal algorithms exist. Am I missing something?
by nine_k 10mo ago
It must be equivalent to the knapsack problem, for which many faster close-to-optimal algorithms exist. Am I missing something?
- layer8 10mo agoIt’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.