Skip to main content

more options


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