He still has to turn in the thesis itself, but my student Josiah Carlson ([info]chouyu_31) passed his final public oral examination today. This seems as good an excuse as any to talk a little about Josiah's thesis work, concerning several problems of optimization in trees.

Optimal pruning

In problems of this type, one is given as input a rooted tree, and must choose a subtree containing the root, optimizing the quality of the chosen subtree. For instance, the tree may represent the branching if-then logic of business planning: if we perform a certain action, we may then take a later action that depends on it. The simplest problem of this type, finding a subtree with maximum profit (given a single variable per node, either a positive profit or a negative cost), is easily solved by a bottom-up traversal of the tree in which one prunes a node whenever the remaining unpruned subtree descending from it has negative total weight.

The optimal pruning problem Josiah studied most closely is a little more complicated: each node has both an eventual profit value and an up-front (positive) cost value, and one wants to maximize return on investment (the total profit divided by the total cost). Josiah found a nice linear time algorithm for this problem, improving a previous O(n log n) solution. His algorithm alternates between two types of logic: a decision subroutine tests whether there is a tree with return on investment larger than a given threshold, using a bottom-up traversal similar to the univariate case, and another subroutine uses the knowledge gained from the decision algorithm to simplify the remaining tree. He also shows that the problem is NP-complete when costs may be negative.

A more general version of the optimal pruning problem, still with two values xi and yi per node, measures the quality of the tree T as F(XT,YT) where XT and YT are the sums of the x's and y's in the unpruned nodes and F is some bivariate function. For instance, certain problems in which nodes have weights that are random variables and one wishes to find a tree that with high probability has low weight can be expressed in this form. If this quality criterion is sufficiently well behaved (maximizing a convex function or minimizing a concave function) then its optimum occurs on a tree T* for which the pair (XT*,YT*) is on the convex hull of the (exponentially many) points (XT,YT) that can be formed for different prunings. This convex hull can be expressed as the sequence of trees minimizing or maximizing λX+Y as λ varies from -∞ to +∞. Thus, one can transform an optimal tree problem with two weights xi and yi per node into a parametric problem in which there is a single weight λxi+yi per node but λ varies. As λ varies, the optimal tree quality λX+Y also varies as a piecewise linear function of λ, with breakpoints whenever the optimal tree changes from one tree to another. Josiah showed how to find these breakpoints in O(n log n) time, by a bottom-up tree traversal in which we calculate these piecewise linear functions using augmented binary search tree data structures to represent them. One interesting special case of this problem is the return on investment problem described above; if F(X,Y) = X/Y, we can find the optimal pruning using parametric techniques whenever all pruned subtrees have YT ≥0, even if some costs are negative. However, the time is slower by a logarithmic factor than when all costs are positive.

We published these results in SWAT 2006; our paper is also online as arxiv:cs.CG/0503023.

Optimal source location

The "simultaneous source location problem" concerns a flow graph in which every edge has a capacity, every node has a demand, and one must choose a subset of nodes to act as sources so that there exists a flow from the sources to all other nodes, satisfying their demands, while not exceeding their edge capacities. It is NP-complete in general for graphs, but metric embedding techniques (e.g. of Fakcharoenphol, Rao, and Talwar, JCSS 2004) can be used to approximate it within a logarithmic factor via a similarly defined problem on trees. Previously, an O(n3) algorithm (with quadratic space) was known for the tree case. The most practically significant of Josiah's new results (but ironically the least publishable, because it's too easy) is a linear time solution when all nodes are allowed to be sources (a property that is fortuitously preserved by the reduction of Fakcharoenphol et al). When only some of the tree nodes may be sources, he shows that the previous solution may be modified to take quadratic time and space. Alternatively, if only the solution quality is needed, but not the actual set of source locations, linear space is possible. Next, he observes that applying the linear space algorithm, then recursing within each subtree, achieves cubic time but now with linear space. Finally, a recursive clustering scheme allows these time and space bounds to be traded off against each other, achieving O(kn2) time and O(n1+1/k) space for any k. Choosing k to be logarithmic in n gives O(n2 log n) time and O(n log n) space, probably the best choice as it matches the time and space bounds of Fakcharoenphol et al.

Optimal-angle tree drawing

The problem here is to draw trees in such a way that the leaves could be extended to infinity without crossing each other, partitioning the plane into convex cells. These drawings have the nice property that the edge lengths can be adjusted arbitrarily, once the angles are fixed, and the drawing will stay planar; we investigated different heuristics for choosing the edge length according to subtree size, or distance from the root, or placing the vertices on concentric circles, although it also works pretty well to keep all edges the same length. But there's a lot of freedom also in choosing the angles, so Josiah's main work in this area was to find an algorithm to optimize the angular resolution of the drawing; that is, to choose the angles to draw the edges of a tree in such a way as to maximize the minimum angle at any vertex. The solution involves some messy case analysis, but leads to linear time algorithms and pretty drawings.

Optimal-angle tree drawing

We published this one in Graph Drawing 2006; it's also online as arxiv:cs.CG/0607113.

Again, congratulations, Josiah!