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 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. In fact, the extent to which such approximation algorithms exist for a problem provides a theoretical yardstick for its actual computational difficulty that is surprisingly accurate. Our work was motivated by the fact that certain linear programming relaxations have been shown to provide extremely good lower bounds on typical data. We provided a theoretical understanding of the strength of these bounds by designing algorithms that "round" the fractional solutions to these linear programs to nearby integer solutions without degrading the quality of the solution too much. PhD student F. Chudak and I developed an algorithm for a basic problem in operations research, the uncapacitated facility problem, which is guaranteed to come within a factor of 1+2/e of optimal. Not only is the theoretical performance of the algorithm surprisingly good, but it is more effective in practice than all previously known heuristic procedures for this problem. We have also begun to investigate algorithms for several capacitated versions of this problem, which arise in a much broader range of applications.