## Books

- D.P. Williamson, D.B. Shmoys.
*The Design of Approximation Algorithms*. Cambridge University Press, 2011. - K. Aardal, J.K. Lenstra, F. Maffioli, and D.B Shmoys (eds.).
*Selected Publications of Eugene L. Lawler*. CWI, 1999. - E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys (eds.).
*The Traveling Salesman Problem.*Wiley, Chichester, 1985.

See books page for details.

## Recent Research Papers

## Sequencing and Scheduling Problems

- H.-C. An, R.D. Kleinberg, and D.B. Shmoys. "Improving Christofides' algorithm for the s-t path TSP," to appear in Proceedings of the 44th Annual ACM Symposium on Theory of Computing, 2012.
- M. Cheung and D.B. Shmoys. "A primal-dual approximation algorithm for min-sum single-machine scheduling problems," Proceeding of APPROX-RANDOM, 2011, 135-146.
- H.-C. An, R.D. Kleinberg, and D.B. Shmoys. "Approximation algorithms for the bottleneck asymmetric traveling salesman problem." Proceedings of APPROX-RANDOM, 2010, 1-11.
- L.A. Hall, A. S. Schulz, D.B. Shmoys, and J. Wein. "Scheduling to minimize average completion time: off-line and on-line approximation algorithms". Mathematics of Operations Research 22, 1997, 513-544. .ps version.
- F.A. Chudak and D.B. Shmoys. "Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds". J. Algorithms 30, 1999, 323-343. [Special issue of selected papers from the 8th Annual ACM-SIAM Symposium on Discrete Algorithms.] .ps version.
- P. Martin and D.B. Shmoys. "A new approach to computing optimal schedules for the job-shop scheduling problem". In Proceedings of the 5th International IPCO Conference, 1996, 389-403. paper.ps tables.ps
- L.A. Hall, D.B. Shmoys, and J. Wein. "Scheduling to minimize average completion time: off-line and on-line algorithms". In the Proceeding of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, 1996, 142-151.
- D.B. Shmoys and E. Tardos, "An approximation algorithm for the generalized assignment problem". Mathematical Programming A 62, 1993, 461-474.

Return to top.

## Stochastic Optimization Problems

- I. Gorodezky, R.D. Kleinberg, D.B. Shmoys, and G. Spencer. Improved Lower Bounds for the Universal and a priori TSP. Proceedings of APPROX-RANDOM, 2010, 178-191.
- D.B. Shmoys and K. Talwar. "A constant approximation algorithm for the a priori TSP," Proceedings of the 13th MPS Conference on Integer Programming and Combinatorial Optimization, 2008, 331-343. .pdf version
- F. Schalekamp and D.B. Shmoys. "Algorithms for the universal and a priori TSP," Operations Research Letters 36, 2008, 1-3. .pdf version
- R. Levi, R. Roundy, D.B. Shmoys, and V.A. Truong. "Approximation algorithms for capacitated stochastic inventory control problems." Operations Research 56, 2008, 1186-1199. .pdf version
- D.B. Shmoys and M. Sozio. "Approximation algorithms for 2-stage stochastic scheduling problems," Proceedings of the 11th MPS Conference on Integer Programming and Combinatorial Optimization, 2007, 145-157. .pdf version
- R. Levi, M. Pal, R. Roundy, and D. Shmoys. "Approximation algorithms for stochastic inventory control models," Mathematics of Operations Research 32, 2007, 284-302. .pdf file of journal version Preliminary version appeared in Proceedings of the 11th MPS Conference on Integer Programming and Combinatorial Optimization, 2005, 306-320.
- R. Levi, R. Roundy, and D.B. Shmoys. "Provably near-optimal sampling-based policies for stochastic inventory control models." Mathematics of Operations Research 32, 2007, 821-839. .pdf file of journal version Preliminary version appeared in Proceedings of STOC 2006, 739-748.
- D.B. Shmoys and C. Swamy. "An approximation scheme for stochastic linear programming and its application to stochastic integer programs." Journal of the ACM 53, 2006, 973-1012. .pdf of the journal version Preliminary version appeared as "Stochastic Optimization is (almost) as Easy as Deterministic Optimization" in Proceedings of FOCS 2004, pages 228-237.
- C. Swamy and D.B. Shmoys. "Sampling-based approximation algorithms for multi-stage stochastic optimization." SIAM J. on Computing 41, 975-1004. [Preliminary version appeared in Proceedings of 45th Annual IEEE Symposium on Foundations of Computer Science, 2005, 357-366.] .ps version

Return to top.

## Facility Location Problems

- T. Carnes and D.B. Shmoys. "Primal-dual schema and Lagrangian relaxation for the k-location-routing problem," Proceedings of APPROX-RANDOM, 2011, 99-110.
- R. Levi, D.B. Shmoys, and C. Swamy.
"LP-based approximation algorithms for capacitated facility location,"
*Mathematical Programming 131*, 2012, 365-379. [Preliminary version appeared in Proceedings of the 10th MPS Conference on Integer Programming and Combinatorial Optimization, 2004, 206-218.] .ps version - C. Swamy and D.B. Shmoys. "Fault-tolerant facility location," ACM Transactions on Algorithms 4, 2008. .pdf file of journal version Preliminary version appeared in Proceedings 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 2003, 735-736.
- D.B. Shmoys, C. Swamy and R. Levi. "Facility location with service installation costs," in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, 2004, 1081-1090. .ps version
- A. Archer, R. Rajagopalan, D.B. Shmoys. "Lagrangian relaxation for the k-median problem: new insights and continuity properties," in Proceedings of the 11th Annual European Symposium on Algorithms, 2003, 31--42. .ps version
- F.A. Chudak and D.B Shmoys. "Improved approximation algorithms for the uncapacitated facility location problem". SIAM J. on Computing 33, 2003, 1-25. .ps version.
- M. Charikar, S. Guha, E. Tardos, and D.B. Shmoys. "A constant-factor approximation algorithm for the k-median problem". Journal Computer System Sciences 65, 2002, 129-149. .ps version.
- K.I. Aardal, F.A. Chudak, and D.B. Shmoys. "Improved approximation algorithms for the k-level facility location problem". Information Processing Letters 72, 1999, 161-167. .ps version.
- F.A. Chudak and D.B. Shmoys. "Improved approximation algorithms for the capacitated facility location problem". In the Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, S875-S876.

Return to top.

## Deterministic Inventory Models

- T. Carnes and D.B. Shmoys. "Primal-Dual Schema for Capacitated Covering Problems", Mathematical Programming A, 1-20, electronically published. [Preliminary version appeared in Proceedings of Integer Programming and Combinatorial Optimization, 2008, 288-302.] .pdf version
- P. Rusmevichientong, C. Tong, H. Topaloglu and D.B. Shmoys. "Assortment optimazation under the multinomial logit model with random choice parameters", Production and Operations Management 23, 2023-2039, 2014.
- R. Levi, R. Roundy, D.B. Shmoys, and M. Sviridenko. "A constant approximation algorithm for the one-warehouse-multi-retailer problem," Management Science 54, 2008, 763-776. .pdf file of journal version Preliminary version appeared in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, 365-374.
- R. Levi, R. Roundy, and D.B. Shmoys. "Primal-dual algorithms for deterministic inventory problems," Mathematics of Operations Research 31, 2006, 267-284. .pdf file of journal version Preliminary version appeared in Proceedings of the 36th Annual Symposium on Theory of Computing, 2004, 353-362.
- R. Levi, J. Geunes, E. Romeijn, and D.B. Shmoys. "Inventory and facility-location models with market selection," Proceedings of the 11th MPS Conference on Integer Programming and Combinatorial Optimization, 2005, 111-124. .ps version.

Return to top.

## Computational Sustainability

- D.B. Shmoys and G. Spencer.
"Approximation algorithms for fragmenting a graph against a stochastically-located threat," Theory Computing
Systems 56, 96-134, 2015. [Preliminary version appeared in
*Proceedings of the 9th Annual Workshop on Approximation and Online Algorithms, Lecture Notes in Computer Science, 7164*.] - D. Sheldon, B. Dilkina, A. Elmachtoub, R. Finseth, A. Sabharwal, J. Conrad, C. Gomes,
D.B. Shmoys, W. Allen, O. Amundsen and W. Vaughn. "Maximizing Spread of Cascades Using Network
Design,"
*Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence: UAI2010*, 2010

Return to top.

## Other Selected Papers

- T. Carnes, S.G. Henderson, M. Ahgari, R. Macdonald and D.B. Shmoys. "Mathematical programming guides air-ambulance routing at Ornge", Interfaces 43, 232-239.
- P. Rusmevichientong, Z.-J. Shen, D.B. Shmoys. "A PTAS for capacitated sum-of-ratios optimization." Operations Research Letters 37, 2009, 230-238.
- C.P. Gomes, R.G. Regis, and D.B. Shmoys. "An improved approximation algorithm for the partial latin square extension problem". Operations Research Letters 32, 2004 479-484. A preliminary version appeared in Proceedings 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 2003, 832-833. .ps version.
- T.J. Vision, D.G. Brown, D.B. Shmoys, R.T. Durrett, and S.D. Tanksley. "Selective mapping: A strategy for optimizing the construction of linkage map." Genetics 155: 407-420, 2000. [ABSTRACT]
- S.A. Plotkin, D.B. Shmoys, E. Tardos. "Fast approximation algorithms for fractional packing and covering problems". Mathematics of Operations Research 20, 1995, 257-301. Preliminary version appeared in the Proceedings of the 32nd Annual IEEE Symposium on the Foundations of Computer Science (1991), 495-504. ORIE TR-999.
- M.X. Goemans, A.V. Goldberg, S. Plotkin, D.B. Shmoys, E. Tardos, and D.P. Williamson. "Improved approximation algorithms for network design problems". In the Proceeding of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (1994), 223-232. ORIE TR-1116.

Return to top.

## Selected Survey Papers

- C. Swamy and D.B. Shmoys. "Approximation algorithms for 2-stage stochastic optimization problems." In Proceedings in FSTTCS 2006, 5-19. .pdf file.
- D.B. Shmoys. "The design and analysis of approximation algorithms: facility location as a case study". In: Trends in Optimization, AMS Proceedings of Symposia in Applied Mathematics 61, (S. Hosten, J. Lee, and R. Thomas, eds.), 2004, 85-97. .ps version
- D.B. Shmoys. "Approximation algorithms for facility location problems". In: Approximation Algorithms for Combinatorial Optimization, Lecture Notes in Computer Science 1913, (K. Jansen and S. Khuller, eds.), Springer, Berlin, 2000, 27-33. .ps version.
- D.B. Shmoys. "Using linear programming in the design and analysis of approximation algorithms: two illustrative problems". In: Approximation Algorithms for Combinatorial Optimization, Lecture Notes in Computer Science 1444 (K. Jansen and J. Rolim, eds.), Springer, Berlin, 1998, 15-32. .ps version.
- D.B. Shmoys. "[Approximation algorithms for] Cut problems and their application to divide-and-conquer". In: Approximation Algorithms for NP-hard Problems, (D.S. Hochbaum, ed.) PWS, 1997, 192-235. .ps version
- A.S. Schulz, D.B. Shmoys, and D.P. Williamson. Approximation algorithms. Proc. National Academy of Sciences 94, 1997, 12734-12735. .pdf version
- D.B. Shmoys and E. Tardos, "Computational complexity".
In: The Handbook of Combinatorics
(R.L. Graham, M. Grotschel, and L. Lovasz, eds.), North Holland, 1995,
1599-1645.
.ps version

This was written during the period 1987-1990, and so is not as recent a survey as its date suggests. Some pointers to more recent work were included in the final stage of publication. - L. Lovasz, D.B. Shmoys and E. Tardos. "Combinatorics in computer science". In: The Handbook of Combinatorics (R.L. Graham, M.Grotschel, and L. Lovasz, eds.) North Holland, 1995, 2003-2038. .ps version
- D.B. Shmoys. "Computing near-optimal solutions to combinatorial optimization problems". In: Combinatorial Optimization, (W. Cook, L. Lovasz, and P.D. Seymour, eds.) AMS, 1995, 355-397. ORIE TR-1120.

Return to top.

## Contact Information

**David B. Shmoys**

Cornell University

214 Rhodes Hall

136 Hoy Road

Ithaca, NY 14853

(607) 255-9146 - phone

(607) 255-9129 - fax