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. Although this work is driven by a theoretical perspective, the ultimate aim is to design algorithms that also work well on problems in real application settings.
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 constant 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. Recent 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 Most recently, we have become interested in developing the needed algorithmic tools for a broad cross-section of applications involving issues in biodiversity, alternative energy logistics, and conservation, which can all come under the common heading of problems in computational sustainability. The primary initiative along these lines has been the development of algorithm tools for operational logistics and design of bike-sharing systems.
A list of selected publications can be found here.
David B. Shmoys
231 Rhodes Hall
Ithaca, NY 14853
(607) 255-9146 - phone
(607) 255-9129 - fax