David Shmoys: Research Interests

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 optimumis also NP-hard. In fact, the extent to which such approximation algorithms exist for a problem provides a surprisingly accurate theoretical yardstick for its actual computational difficulty.

Our work has been 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. We have obtained the first constan performance guarantees for several problems central to the discrete optimization literature, including the k-center and k-median problems, generalized assignment problem, as well as a variety of scheduling problem in which the aim is to minimized the average job completion time. Current work includes the application of discrete optimization techniques to several issues in comptuational biology, as well as in stochastic model for clustering and inventory theory

• Go to Selected Publications

Back to Cornell ORIE