The primary focus of my research is on the design and analysis of efficient algorithms for discrete optimization problems, and in particular, on approximation algorithms for NP-hard and other computationally intractable problems. Computational complexity theory provides a mathematical foundation for the intractability of many computational problems by proving that all NP-complete problems are equally hard. However, in practice, real-world inputs for some NP-hard optimization problems are straightforward to solve, whereas for others, even quite modestly-sized inputs are beyond the limits of the most sophisticated methods. Analogously, from a theoretical perspective, for some NP-hard optimization problems it is possible to efficiently compute solutions that are guaranteed to be arbitrarily close to optimal, whereas for others, computing even a crude approximation to the optimum is also NP-hard.

We are interested in the development of algorithmic tools that lead to approximation algorithms for which good performance guarantees can be proved. In particular, we have been exploring the role that mathematical programming relaxations can play in the design of approximation algorithms. We have been studying a variety of clustering problems, facility location problems, inventory problems, as well as sequencing and scheduling problems from this perspective. Since the primary means of solving these problems (to optimality) also involves the solution of a sequence of such relaxations, this algorithmic approach dovetails well with the foremost technology for proving optimality, and hence has substantial potential for improving these optimization techniques as well. Most recently, we have begun to investigate the design of approximation algorithms with provable performance guarantees for stochastic programming problems in such settings as inventory control and other logistics problems.