Books
 Jan Karel Lenstra and David B. Shmoys. Elements of Scheduling. CoRR abs/2001.06005 (2020) http://arxiv.org/abs/2001.06005.
 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
DataDriven DecisionMaking in Enterprise & Society
 P. I. Frazier, J. M. Cashore, N. Duan, S. G. Henderson, A. Janmohamed, B. Liu, D. B. Shmoys, J. Wan, and Y. Zhang. "Modeling for COVID19 college reopening decisions: Cornell, a case study", Proceedings of the National Academy of Sciences 119, e2112532119 (2022).
 N. Garg, W. Gurnee, D. Rothschild, David B. Shmoys. "Combatting Gerrymandering with Social Choice: the Design of Multimember Districts". CoRR abs/2107.07083 (2021)
 W. Gurnee, D.B. Shmoys. "Fairmandering: A column generation heuristic for fairnessoptimized political districting." Proceedings of the 2021 SIAM Conference on Applied and Computational Discrete Algorithms (ACDA 2021), 2021, 8899. PDF  TXT
Awarded Best Paper Prize.  Daniel Freund, Shane G. Henderson, Eoin O'Mahony, David B. Shmoys. "Analytics and Bikes: Riding Tandem with Motivate to Improve Mobility", INFORMS J. on Applied Analytics 49, 2019, 310323.
2018 Wagner Prize Article.  H. Chung, D. Freund, and D.B. Shmoys. "Bike Angels: An Analysis of Citi Bike's I
ncentive Program," ACM COMPASS 2018, 5:15:9.
Awarded Best Paper Prize.  D. Freund, S.G. Henderson, and D.B. Shmoys. "Minimizing Multimodular Functions and Allocating Capacity in BikeSharing Systems," 2017 MOS Conference on Integer Programming and Combinatorial Optimization (IPCO), 2017, 186198.
 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, 687694.
 T. Carnes, S.G. Henderson, D.B. Shmoys, M. Ahgari and R. Macdonald. "Mathematical programming guides airambulance routing at Ornge", Interfaces 43, 2013, 232239. PDF  TXT
Other Papers on Computational Sustainability
 Carla P. Gomes, Thomas G. Dietterich, Christopher Barrett, Jon Conrad, Bistra Dilkina, Stefano Ermon, Fei Fang, Andrew Farnsworth, Alan Fern, Xiaoli Z. Fern, Daniel Fink, Douglas H. Fisher, Alexander Flecker, Daniel Freund, Angela Fuller, John M. Gregoire, John E. Hopcroft, Steve Kelling, J. Zico Kolter, Warren B. Powell, Nicole D. Sintov, John S. Selker, Bart Selman, Daniel Sheldon, David B. Shmoys, Milind Tambe, WengKeen Wong, Christopher Wood, Xiaojian Wu, Yexiang Xue, Amulya Yadav, AbdulAziz Yakubu, Mary Lou Zeeman. "Computational sustainability: computing for a better world and a sustainable future", Communications of the ACM 62, 2019, 5665.
 D.B. Shmoys and G. Spencer. "Approximation algorithms for fragmenting a graph against a stochasticallylocated threat," Theory Computing Systems 56, 96134, 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.
Sequencing and Scheduling Problems
 H.C. An, R. Kleinberg, D.B. Shmoys. "Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem" ACM Transactions on Algorithms 17, 2021, 35:135:12. [Preliminary version appeared in Proceedings of APPROXRANDOM, 2010.]
 Alice Paul, Daniel Freund, Aaron M. Ferber, David B. Shmoys, David P. Williamson. "Budgeted PrizeCollecting Traveling Salesman and Minimum Spanning Tree Problems", Mathematics of Operations Research 45, 2020, 576590. [Preliminary Version appeared in European Symposium on Algorithms, 2017.]
 S. Agarwal, S. Rajakrishnan, A. Narayan, R. Agarwal, D.B. Shmoys and A. Vahdat. "Sincronia: NearOptimal 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 st 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 primaldual approximation algorithm for minsum singlemachine scheduling problems". SIAM J. on Discrete Mathematics 31, 825838. [Preliminary version appeared in Proceedings of APPROXRANDOM 2011.]
 P.R. Steele, S.G. Henderson, and D.B. Shmoys. "Aggregating courier deliveries". Naval Logistics Research 65,187202, 2018.
 L.A. Hall, A. S. Schulz, D.B. Shmoys, and J. Wein. "Scheduling to minimize average completion time: offline and online approximation algorithms". Mathematics of Operations Research 22, 1997, 513544. PDF  TXT.
 F.A. Chudak and D.B. Shmoys. "Approximation algorithms for precedenceconstrained scheduling problems on parallel machines that run at different speeds". J. Algorithms 30, 1999, 323343. [Special issue of selected papers from the 8th Annual ACMSIAM Symposium on Discrete Algorithms.] PDF  TXT.
 P. Martin and D.B. Shmoys. "A new approach to computing optimal
schedules for the jobshop scheduling problem". In Proceedings of the
5th International IPCO Conference, 1996, 389403.
Paper PDF  Paper TXT
Tables PDF  L.A. Hall, D.B. Shmoys, and J. Wein. "Scheduling to minimize average completion time: offline and online algorithms". In the Proceeding of the 7th Annual ACMSIAM Symposium on Discrete Algorithms, 1996, 142151.
 D.B. Shmoys and E. Tardos, "An approximation algorithm for the generalized assignment problem". Mathematical Programming A 62, 1993, 461474.
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 APPROXRANDOM, 2010, 178191.
 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, 331343. PDF  TXT
 F. Schalekamp and D.B. Shmoys. "Algorithms for the universal and a priori TSP," Operations Research Letters 36, 2008, 13. PDF  TXT
 R. Levi, R. Roundy, D.B. Shmoys, and V.A. Truong. "Approximation algorithms for capacitated stochastic inventory control problems." Operations Research 56, 2008, 11861199. PDF  TXT
 D.B. Shmoys and M. Sozio. "Approximation algorithms for 2stage stochastic scheduling problems," Proceedings of the 11th MPS Conference on Integer Programming and Combinatorial Optimization, 2007, 145157. PDF  TXT
 R. Levi, M. Pal, R. Roundy, and D. Shmoys.
"Approximation algorithms for stochastic inventory control models,"
Mathematics of Operations Research 32, 2007, 284302.
Journal Version PDF  Journal Version TXT
Preliminary version appeared in Proceedings of the 11th MPS Conference on Integer Programming and Combinatorial Optimization, 2005, 306320.  R. Levi, R. Roundy, and D.B. Shmoys.
"Provably nearoptimal samplingbased policies for stochastic inventory
control models."
Mathematics of Operations Research 32, 2007, 821839.
Journal Version PDF  Journal Version TXT
Preliminary version appeared in Proceedings of STOC 2006, 739748.  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, 9731012.
Journal Version PDF  Journal Version TXT
Preliminary version appeared as "Stochastic Optimization is (almost) as Easy as Deterministic Optimization" in Proceedings of FOCS 2004, pages 228237.  C. Swamy and D.B. Shmoys. "Samplingbased approximation algorithms for multistage stochastic optimization." SIAM J. on Computing 41, 9751004. [Preliminary version appeared in Proceedings of 45th Annual IEEE Symposium on Foundations of Computer Science, 2005, 357366.] PDF  TXT
Return to top.
Facility Location Problems
 Omar El Housni, Vineet Goyal, David B. Shmoys. "On the Power of Static Assignment Policies for Robust Facility Location Problems", Proceedings of the 2021 MOS Conference on Integer Programming and Combinatorial Optimization (IPCO), 2021, 252267. PDF  TXT
 T. Carnes and D.B. Shmoys. "Primaldual schema and Lagrangian relaxation for the klocationrouting problem," Proceedings of APPROXRANDOM, 2011, 99110.
 R. Levi, D.B. Shmoys, and C. Swamy. "LPbased approximation algorithms for capacitated facility location," Mathematical Programming 131, 2012, 365379. [Preliminary version appeared in Proceedings of the 10th MPS Conference on Integer Programming and Combinatorial Optimization, 2004, 206218.] PDF  TXT
 C. Swamy and D.B. Shmoys.
"Faulttolerant facility location,"
ACM Transactions on Algorithms 4, 2008.
Journal Version PDF  Journal Version TXT
Preliminary version appeared in Proceedings 14th Annual ACMSIAM Symposium on Discrete Algorithms, 2003, 735736.  D.B. Shmoys, C. Swamy and R. Levi. "Facility location with service installation costs," in Proceedings of the 15th Annual ACMSIAM Symposium on Discrete Algorithms, 2004, 10811090. PDF  TXT
 A. Archer, R. Rajagopalan, D.B. Shmoys. "Lagrangian relaxation for the kmedian problem: new insights and continuity properties," in Proceedings of the 11th Annual European Symposium on Algorithms, 2003, 3142. PDF  TXT
 F.A. Chudak and D.B Shmoys. "Improved approximation algorithms for the uncapacitated facility location problem". SIAM J. on Computing 33, 2003, 125. PDF  TXT.
 M. Charikar, S. Guha, E. Tardos, and D.B. Shmoys. "A constantfactor approximation algorithm for the kmedian problem". Journal Computer System Sciences 65, 2002, 129149. PDF  TXT.
 K.I. Aardal, F.A. Chudak, and D.B. Shmoys. "Improved approximation algorithms for the klevel facility location problem". Information Processing Letters 72, 1999, 161167. PDF  TXT.
 F.A. Chudak and D.B. Shmoys. "Improved approximation algorithms for the capacitated facility location problem". In the Proceedings of the 10th Annual ACMSIAM Symposium on Discrete Algorithms, 1999, S875S876.
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, 207233.
 T. Carnes and D.B. Shmoys. "PrimalDual Schema for Capacitated Covering Problems", Mathematical Programming A, 120, electronically published. [Preliminary version appeared in Proceedings of Integer Programming and Combinatorial Optimization, 2008, 288302.] PDF  TXT
 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, 20232039, 2014.
 R. Levi, R. Roundy, D.B. Shmoys, and M. Sviridenko.
"A constant approximation algorithm for the onewarehousemultiretailer
problem,"
Management Science 54, 2008, 763776.
Journal Version PDF  Journal Version TXT
Preliminary version appeared in Proceedings of the 15th Annual ACMSIAM Symposium on Discrete Algorithms, 2005, 365374.  R. Levi, R. Roundy, and D.B. Shmoys.
"Primaldual algorithms for deterministic inventory problems,"
Mathematics of Operations Research 31, 2006, 267284.
Journal Version PDF  Journal Version TXT
Preliminary version appeared in Proceedings of the 36th Annual Symposium on Theory of Computing, 2004, 353362.  R. Levi, J. Geunes, E. Romeijn, and D.B. Shmoys. "Inventory and facilitylocation models with market selection," Proceedings of the 11th MPS Conference on Integer Programming and Combinatorial Optimization, 2005, 111124. PDF  TXT.
Return to top.
Other Selected Papers

<
 P. Rusmevichientong, Z.J. Shen, D.B. Shmoys. "A PTAS for capacitated sumofratios optimization." Operations Research Letters 37, 2009, 230238.
 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 479484. A preliminary version appeared in Proceedings 14th Annual ACMSIAM Symposium on Discrete Algorithms, 2003, 832833. PDF  TXT.
 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: 407420, 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, 257301. Preliminary version appeared in the Proceedings of the 32nd Annual IEEE Symposium on the Foundations of Computer Science (1991), 495504. ORIE TR999.
 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 ACMSIAM Symposium on Discrete Algorithms (1994), 223232. ORIE TR1116.
Return to top.
Selected Survey Papers
 C. Swamy and D.B. Shmoys. "Approximation algorithms for 2stage stochastic optimization problems." In Proceedings in FSTTCS 2006, 519. PDF  TXT.
 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, 8597. PDF  TXT
 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, 2733. PDF  TXT.
 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, 1532. PDF  TXT.
 D.B. Shmoys. "[Approximation algorithms for] Cut problems and their application to divideandconquer". In: Approximation Algorithms for NPhard Problems, (D.S. Hochbaum, ed.) PWS, 1997, 192235. PDF  TXT
 A.S. Schulz, D.B. Shmoys, and D.P. Williamson. Approximation algorithms. Proc. National Academy of Sciences 94, 1997, 1273412735. PDF
 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,
15991645. PDF  TXT
This was written during the period 19871990, 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.
An earlier, more extensive version was published as a Cornell Technical Report. PDF  TXT
 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, 20032038. PDF  TXT
 D.B. Shmoys. "Computing nearoptimal solutions to combinatorial optimization problems". In: Combinatorial Optimization, (W. Cook, L. Lovasz, and P.D. Seymour, eds.) AMS, 1995, 355397. PDF  TXT.
Return to top.
Contact Information
David B. Shmoys
Cornell University
231 Rhodes Hall
136 Hoy Road
Ithaca, NY 14853
(607) 2559146  phone
(607) 2559129  fax