- INSTANCE: Directed graph , edge costs , root , set of terminals of size .
- SOLUTION: A directed tree in G rooted at such that , .
- COST FUNCTION: .
- OBJECTIVE: Minimize.
*Approx.:*Approximable within approximation ratio for every [27].*Hardness:*For every fixed cannot be approximated within ratio , unless [61].*Comment:*Admits a -approximation algorithm with running time , for any integer , where t is the number of terminals. This gives a -approximation algorithm with running time for any fixed , and an -approximation in quasi-polynomial time [109], [79], [80], [60].

2015-04-27 Revision: 288 PDF version