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. Computer Science: An Interdisciplinary Approach, Addison-Wesley Professional, 2016, ISBN 0-134-07642-7.
- Robert Sedgewick, Kevin Wayne, and Robert Dondero. Introduction to Programming in Python: An Interdisciplinary Approach, Addison-Wesley Professional, 2015, ISBN 9-332-57743-9.
- 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.