Algorithms

Adrian Lewis does research on numerical methods for nonsmooth optimization problems (e.g., random gradient sampling techniques, subgradient bundling approaches, space dilation), as well as research on algorithms for convex problems (e.g., interior point methods, constructions using hyperbolic polynomials). Of particular interest to him are computational methods in the context of semidefinite programming and in the context of matrix pseudospectra, a robust analogue of the spectrum.

James Renegar works on algorithmic problems possessing a combination of numerical analysis and algebra (e.g., approximating roots of polynomials, decision and quantifier elimination methods for the first-order theory of the reals, interior-point methods for algebraic convex optimization problems). He has laid theoretical foundations for round-off error analysis of algorithms for convex optimization. Currently he is pursuing hyperbolic programming, where he is devising algorithms that generalize interior-point methods.

Robin Roundy pursues research emphasizing efficient approximation algorithms for problems in both deterministic and stochastic inventory management, and in facility location.

David Shmoys focuses on algorithms for discrete optimization problems, in a wide variety of application areas. He is particularly interested in devising efficient approximation algorithms for intractable problems. A recurring characteristic of his approximation algorithms is the use of linear programming in novel ways. Application areas to which he has contributed include numerous traditional operations research logistics problems, but also include issues such as genetic linkage mapping (identifying the locations of markers on the genome) to reduce the cost of wet lab experiments and improve the accuracy of the resulting maps.

Eva Tardos (Department of Computer Science) works on efficient algorithms for problems in combinatorial optimization on graphs and network. Such problems arise in many applications such as vision, and the design, maintenance, and management of communication networks. She is mostly interested in fast combinatorial algorithms that provide provably optimal or close-to-optimal results.

Michael Todd is interested in polynomial-time algorithms for linear and semidefinite programming, including software development. He has also worked on analysis of the simplex method, the ellipsoid method, and simplicial algorithms for fixed-point problems and computing economic equilibria, and is currently working on first-order methods for nonsmooth optimization.

Huseyin Topaloglu does research on transportation models. The focus of his research is to make dynamic programming work for large-scale applications where the state variables are typically vectors with thousands of dimensions. For this purpose, he uses ideas from classical Markov decision theory and stochastic approximation algorithms, and seeks to exploit structural properties (e.g., monotonicity, convexity, submodularity) of the underlying problem to enhance computational performance.

Leslie Trotter does design and analysis of algorithms for integer programming and combinatorial optimization. He is particularly interested in software development of parallel computing algorithms and computational experimentation with large-scale discrete optimization models.

David Williamson has worked on designing approximation algorithms for problems in network design, satisfiability, graph cuts, scheduling, facility location, clustering, feedback vertex sets, and other areas. He has used various tools from mathematical programming to design good approximation algorithms, including the primal-dual method and semidefinite programming.