# ICS 269, Spring 2005: Theory Seminar

## 22 Apr 2005:

The Maximum-Mean Subtree

Josiah Carlson

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.