Skip to content
Better HN
Top
Best
Ask
Show
New
Jobs
Search
⌘K
0 points
nine_k
5mo ago
0 comments
Save
Share
It must be equivalent to the knapsack problem, for which many faster close-to-optimal algorithms exist. Am I missing something?
0 comments
1 comments · 1 top-level
top
newest
oldest
layer8
5mo 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
