Skip to main content

more options


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


Data-Driven Decision-Making 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 COVID-19 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 Multi-member Districts". CoRR abs/2107.07083 (2021)
  • W. Gurnee, D.B. Shmoys. "Fairmandering: A column generation heuristic for fairness-optimized political districting." Proceedings of the 2021 SIAM Conference on Applied and Computational Discrete Algorithms (ACDA 2021), 2021, 88-99. 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, 310-323.
    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:1-5:9.
    Awarded Best Paper Prize.
  • 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.
  • 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.
  • T. Carnes, S.G. Henderson, D.B. Shmoys, M. Ahgari and R. Macdonald. "Mathematical programming guides air-ambulance routing at Ornge", Interfaces 43, 2013, 232-239. 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, Weng-Keen Wong, Christopher Wood, Xiaojian Wu, Yexiang Xue, Amulya Yadav, Abdul-Aziz Yakubu, Mary Lou Zeeman. "Computational sustainability: computing for a better world and a sustainable future", Communications of the ACM 62, 2019, 56-65.
  • 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.

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:1-35:12. [Preliminary version appeared in Proceedings of APPROX-RANDOM, 2010.]
  • Alice Paul, Daniel Freund, Aaron M. Ferber, David B. Shmoys, David P. Williamson. "Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems", Mathematics of Operations Research 45, 2020, 576-590. [Preliminary Version appeared in European Symposium on Algorithms, 2017.]
  • S. Agarwal, S. Rajakrishnan, A. Narayan, R. Agarwal, D.B. Shmoys 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.
  • 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. PDF | TXT.
  • 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.] PDF | TXT.
  • 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 PDF | Paper TXT
    Tables PDF
  • 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 | TXT
  • F. Schalekamp and D.B. Shmoys. "Algorithms for the universal and a priori TSP," Operations Research Letters 36, 2008, 1-3. 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, 1186-1199. PDF | TXT
  • 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 | TXT
  • R. Levi, M. Pal, R. Roundy, and D. Shmoys. "Approximation algorithms for stochastic inventory control models," Mathematics of Operations Research 32, 2007, 284-302. Journal Version PDF | Journal Version TXT
    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. Journal Version PDF | Journal Version TXT
    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. 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 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.] 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, 252-267. PDF | TXT
  • 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.] PDF | TXT
  • C. Swamy and D.B. Shmoys. "Fault-tolerant facility location," ACM Transactions on Algorithms 4, 2008. Journal Version PDF | Journal Version TXT
    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. PDF | TXT
  • 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. PDF | TXT
  • F.A. Chudak and D.B Shmoys. "Improved approximation algorithms for the uncapacitated facility location problem". SIAM J. on Computing 33, 2003, 1-25. PDF | TXT.
  • 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. PDF | TXT.
  • 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. 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 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 | 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, 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. Journal Version PDF | Journal Version TXT
    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. Journal Version PDF | Journal Version TXT
    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. PDF | TXT.


Return to top.


Other Selected Papers


    <
  • 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. 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: 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 | 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, 85-97. 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, 27-33. 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, 15-32. PDF | TXT.
  • 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. PDF | TXT
  • A.S. Schulz, D.B. Shmoys, and D.P. Williamson. Approximation algorithms. Proc. National Academy of Sciences 94, 1997, 12734-12735. 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, 1599-1645. PDF | TXT
    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.

    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, 2003-2038. PDF | TXT
  • 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. PDF | TXT.

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