“A spanning tree T of graph G is a ρ-approximate universal Steiner tree (UST) for root vertex r if, for any subset of vertices S containing r, the cost of the minimal subgraph of T connecting S is within a ρ factor of the minimum cost tree connecting S in G. … We settle [several] open questions by giving polynomial-time algorithms for computing both O(log7n)-approximate USTs and poly-logarithmic strong sparse partition hierarchies.”

Find the paper and full list of authors at ArXiv.