Expand description
Tree trimming algorithms by budget.
Algorithm selection depends on tree size:
- < 100 nodes: Tree Knapsack DP (exact optimum)
- 100-999: Greedy fractional (>= 63% of optimum, ~90%+ in practice)
- 1000-9999: Hierarchical WFQ (proportionally fair)
-
= 10000: Head+Tail linear (heuristic for logs)
Modules§
- greedy
- Greedy fractional — for trees with 100-999 nodes.
- head_
tail - Head+Tail linear trimming — heuristic for trees > 10000 nodes.
- knapsack
- Tree Knapsack DP — exact optimum for trees with < 100 nodes.
- wfq
- Hierarchical Weighted Fair Queuing — for trees of 1000-9999 nodes.
Functions§
- trim
- Trim the tree to fit the budget, automatically selecting the optimal algorithm.