## 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

- S. Agarwal, S. Rajakrishnan, A. Narayan, R. Agarwal, and A. Vahdat. "Sincronia: Near-Optimal Network Design for Coflows,"
*ACM SIGCOMM 2018*, 16 -- 29. {Awarded Best Student Paper Prize}. - H.-C. An, R. Kleinberg, and D.B. Shmoys. "Improving Christofides' algorithm for the s-t path TSP",
*J. Assoc. Comput. Mach.*62, article 34, 2015. [Preliminary version appeared in*Proceedings of the 44th Annual ACM Symposium on Theory of Computing*.]. - M. Cheung, J. Mestre, D.B. Shmoys, and J. Verschae. "A primal-dual approximation algorithm for min-sum single-machine scheduling problems".
*SIAM J. on Discrete Mathematics*31, 825--838. [Preliminary version appeared in*Proceedings of APPROX-RANDOM 2011*.] - P.R. Steele, S.G. Henderson, and D.B. Shmoys. "Aggregating courier deliveries".
*Naval Logistics Research 65*,187-202, 2018. - A. Paul, D. Freund, A. Ferber, D.B. Shmoys, and D.P. Williamson, "Budgeted prize-collecting traveling salesman and minimum spanning tree problems",
*European Symposium on Algorithms*, 2017, 62:1--62:14. - 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

- M. Cheung, A.N. Elmachtoub, R. Levi, and D.B. Shmoys. "The submodular joint replenishment problem",
*Mathematical Programming*158, 207-233. - 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 (including bike-sharing)

- 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 - D. Freund, S.G. Henderson, and D.B. Shmoys. "Minimizing Multimodular Functions and Allocating Capacity in Bike-Sharing Systems,"
*2017 MOS Conference on Integer Programming and Combinatorial Optimization (IPCO)*, 2017, 186--198. - H. Chung, D. Freund, and D.B. Shmoys. "Bike Angels: An Analysis of Citi Bike's Incentive Program,"
*ACM COMPASS 2018*, 5:1-5:9. Awarded Best Paper Prize. - E. O'Mahony and D.B. Shmoys. "Data Analysis and Optimization for (Citi)Bike Sharing,"
*Proceedings of the 29th Conference on Artificial Intelligence (AAAI)*, 2015, 687--694.

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

231 Rhodes Hall

136 Hoy Road

Ithaca, NY 14853

(607) 255-9146 - phone

(607) 255-9129 - fax