# Research

## Academic History

I have a B.S. from Yale in Applied Mathematics and a Ph.D. from Cornell University in Operations Research and Information Engineering. My thesis research was supervised by Éva Tardos.

## Research Interests

My research is in theoretical computer science, especially optimization, combinatorics and the design, analysis, and implementation of computer algorithms. Currently, I am working on the design, analysis, and efficient implementation of polynomial-time algorithms for network flow problems, including generalized flows and multicommodity flows. Generalized flows model the shipment of a single commodity though a network which "leaks." Some applications include shipping oil, optimal currency conversion, and scheduling. Multicommodity flows can model the shipment of several commodities through a common network. Some applications include: routing communication messages, VLSI design, and maintaining sparsity with Gaussian elimination.

## Selected Publications

- Robert Sedgewick and Kevin Wayne.
*Algorithms, 4th Edition*. Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. - Robert Sedgewick and Kevin Wayne.
*Introduction to Programming in Java: An Interdisciplinary Approach*. Addison-Wesley, 2007. ISBN 0-321-49805-4. - Lisa Fleischer and Kevin Wayne.
*Faster Approximation Algorithms for Generalized Network Flow*. Preliminary version in 10th Annual ACM-SIAM Symposium on Discrete Algorithms. Journal version of a generalization appears in Mathematical Programming, pp. 215-238, Vol. 91, No. 2. Talk. - Jon Lee, Chun-Wa Ko, and Kevin Wayne.
*Comparisons of Spectral and Hadamard Bounds for D-Optimality*, in Model-Oriented Data Analysis and Experimental Design, Contribution to Statistics, Springer, Berlin, 21-29. -
Éva Tardos and Kevin Wayne.
*Simple Generalized Maximum Flow Algorithms*, Integer Programming and Combinatorial Optimization, pp. 310-324, Lecture Notes in Computer Science, vol. 1412, Springer. Talk. - Kevin Wayne.
*Generalized Maximum Flow Algorithms*, Ph.D. dissertation, Cornell University. - Kevin Wayne.
*A New Property and Faster Algorithm for Baseball Elimination*. Preliminary version in 10th Annual ACM-SIAM Symposium of Discrete Algorithms. Journal version in SIAM Journal on Discrete Mathematics, pp. 223-229, Vol. 14, No. 2. Talk. - Kevin Wayne.
*A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow*. Preliminary version in 31st Annual Symposium on Theory of Computation. Journal version in Mathematics of Operations Research, pp. 445-459, Vol. 27, No. 3. Talk.