undefined | Better HN

0 pointsnine_k2mo ago0 comments

It must be equivalent to the knapsack problem, for which many faster close-to-optimal algorithms exist. Am I missing something?

0 comments

layer82mo ago

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.

j / k navigate · click thread line to collapse

0 pointsnine_k2mo ago0 comments

It must be equivalent to the knapsack problem, for which many faster close-to-optimal algorithms exist. Am I missing something?

0 comments

layer82mo ago

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.

j / k navigate · click thread line to collapse