Algorithms, Network Design and Analysis, Optimization, Supply Chain Management

Office: 232 Rhodes

Phone: 607.255.9146

Website: click here

Fax: 607.255.9129

David Shmoys obtained his Ph.D. in Computer Science from the University of California at Berkeley in 1984. He has faculty appointments in both the School of Operations Research and Industrial Engineering and the Department of Computer Science. Shmoys’ research has focused on the design and analysis of efficient algorithms for discrete optimization problems.

His work has highlighted the central role that linear programming plays in the design of approximation algorithms for NP–hard problems. In particular, he is known for his results on scheduling and clustering problems, including the first constant-performance guarantees for several problems central to the literature, including the k-center and k-median problems, the generalized assignment problem, as well as scheduling problems in which the aim is to minimize the average job-completion time. His work on polynomial-time approximation schemes for scheduling problems introduced techniques that have subsequently been applied to a variety of other settings. His current work includes the application of discrete optimization techniques to several issues in computational biology, as well as in the development of approximation algorithms for stochastic models of clustering, inventory, and related problems in logistics.

Select Publications

"Approximation Algorithms for Stochastic Inventory Control Models". In Proceedings of the 11th MPS Conference on Integer Programming and Combinatorial Optimization 306-320 (June 2005). (With R. Levi, M. Pal, and R. Roundy)

"A Constant Approximation Algorithm for the One-Warehouse-Multi-Retailer Problem". In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, 365-375 (January 2005). (With R. Levi and R. Roundy)

"Stochastic Optimization is (Almost) as Easy as Deterministic Optimization". In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science 228-237 (October 2004). (With C. Swamy)

"Primal-dual Algorithms for Deterministic Inventory Problems". In Proceedings of the 36th Annual Symposium on Theory of Computing 353-362 (June 2004). (With R. Levi and R. Roundy)

"The Design and Analysis of Approximation Algorithms: Facility Location as a Case Study". In Trends in Optimization, American Mathematical Society (AMS) Proceedings of Symposia in Applied Mathematics (S. Hosten, J. Lee, and R. Thomas, eds.) (June 2004).

"Facility Location with Service-installation Costs". In Proceedings of the Fifteenth Annual ACM- SIAM Symposium on Discrete Algorithms 1081-1090 (January 2004).(With C. Swamy and R. Levi)

"Improved Approximation Algorithms for the Uncapacitated Facility Location Problem". SIAM Journal on Computing 33: 1-25 (2003). (With F. Chudak)

"A Constant-factor Approximation Algorithm for the k-median Problem". Journal of Computer and System Sciences 65:129-149 (2002). (With M. Charikar, S. Guha, and E. Tardos)

Lectures

Approximation Algorithms for Stochastic Programming Problems. New Horizons in Computing, Recent Trends in Theoretical Computer Science. Invited Plenary Speaker. Kyoto, Japan. (February 2005).

Approximation Algorithms for Stochastic Inventory Control Models. 11th MPS Conference on Integer Programming and Combinatorial Optimization, Berlin, Germany (June 2005).

The Design and Analysis of Approximation Algorithms: Facility Location as a Case Study. Short Course on Trends in Optimization, AMS National Meeting, Phoenix. (January 2004).

Stochastic Optimization is (Almost) as Easy as Deterministic Optimization. 45th Annual IEEE Symposium on Foundations of Computer Science, Rome, Italy (October 2004) and Bertinoro Workshop on Combinatorial Optimization, Bertinoro, Italy (May 2004).

Professional Activities

Member, Editorial Board, SIAM Journal on Discrete Mathematics

Associate Editor, Mathematical Programming

Publications Chair, Mathematical Programming Society

Prize Coordinator, SIGACT (Special Interest Group on Algorithms and Computation Theory), ACM

University Activities

Ad Hoc Committee of the Dean and the Faculty on Course and Exam Scheduling

Awards and Recognition

ACM Fellow

College of Engineering Sonny Yau Excellence in Teaching Award (three times)

NSF Presidential Young Investigator Award