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.