Lisa K. Fleischer
Associate Professor of Operations Research

A.B.,Harvard College, 1989;
M.A., Cornell University, 1995;
Ph.D., 1997

Personal Web Page: http://www.andrew.cmu.edu/user/lkf/

Teaching and Research Interests:

Discrete optimization, approximation algorithms, network routing and design, linear and integer programming.

Major Publications/Papers:

"A Push-Relabel Framework for Submodular Function Minimization and Applications to Parametric Optimization," with S. Iwata, to appear in Discrete Applied Math, Special issue on matroids and submodular optimization, Editor: S. Fujishige;

"A Faster Capacity Scaling Algorithm for Minimum Cost Submodular Flow," with Satoru Iwata and S. Thomas McCormick, Math. Programming A 92, 1, 119-139, 2002;

"The Quickest Multicommodity Flow Problem," with M. Skutella, Integer Programming and Combinatorial Optimization (IPCO) Conference Proceedings, LNCS 2337, 36-53, May 2002;

"An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem," with K. Jain and D. P. Williamson, Proceedings of 42nd Annual Symposium on Foundations of Computer Science (FOCS), pp.339-347, October 2001;

"A 2-Approximation for Minimum Cost {0,1,2} Vertex Connectivity," Integer Programming and Combinatorial Optimization (IPCO) Conference Proceedings, LNCS 2081, pp. 115-129, June 2001;

"A Combinatorial, Strongly Polynomial-Time Algorithm for Minimizing Submodular Functions," with S. Iwata and S. Fujishige, Journal of the ACM, 48, 4, 761-777, 2001;

"Improved Algorithms for Submodular Function Minimization and Submodular Flow," with S. Iwata, Proc. 32nd ACM Symp. Theory of Computing, 107-116, May 2000;

"Approximating Fractional Multicommodity Flows Independent of the Number of Commodities," SIAM J. Discrete Math. 13, No. 4, pp. 505-520, 2000;

"Strengthening the Integrality Gaps for Capacitated Network Design and Covering Problems," with R. D. Carr, C. A. Phillips, and V. J. Leung, Proc. 32nd ACM/SIAM Symposium on Discrete Algorithms, 106-115, 2000;

"Separating Maximally Violated Combs in Planar Graphs," with É. Tardos, Mathematics of Operations Research, 24, 1, pp. 130-148, 1999

Awards/Honors:

• NSF Career Award, 2000-2004
• NSF International Fellow Postdoctoral Award, 1999
• INFORMS George Nicholson Prize, 1998

Editorial Boards:

• Associate Editor, Operations Research, 2000-
• Associate Editor, Operations Research Letters, 2002-