In this talk, we define the Maximum-Mean Subtree problem on trees, an equivalent reformulation of the Fractional Prize-Collecting Steiner Tree Problem on Trees. We describe an algorithm that solves the Maximum-Mean Subtree problem, and prove that our algorithm runs in O(n) time in the worst case, improving a previous O(n log n) algorithm.
This talk is a presentation of a paper by David Eppstein and Josiah Carlson, which was submitted to WADS 2005.