Ph.D., August 1999. Worked on experimental and theoretical analysis of network flow algorithms. Advisor: Serge Plotkin. National Science Foundation Graduate Student Fellow.

Thesis title: *Multicommodity and Generalized Flow Algorithms: Theory and Practice.* Multicommodity flow problems involve
simultaneously shipping multiple commodities through a single network
so the total (multi)flow obeys arc capacity constraints. Theoretical
work yielded combinatorial approximation algorithms for the no-cost
and the minimum-cost problem variants with provably small running
times and space requirements. Unfortunately, a direct implementation
of the theories is not fast. I designed and evaluated algorithms
which are experimentally fast while maintaining the same asymptotic
complexity. These implementations are several orders of magnitude
faster than commercial linear programming solvers.

Generalized flow problems generalize ordinary network flow problems by adding a flow multiplier to each arc. Because these problems can have full rank, these generalized network flow problems have appeared more difficult to solve than ordinary network flow problems. I showed how to combine parametric search and the Bellman-Ford shortest path framework to solve a generalized shortest path problem. Using this algorithm as a subroutine, I presented combinatorial, fully polynomial-time approximation schemes for all generalized flow problems (with nonnegative costs).

Graduated summa cum laude. National Merit Scholar. Tau Beta Pi.