David B. Shmoys
School of Operations Research and Information Engineering

Selected Recent Research Papers

Approximation Algorithms for Stochastic Programming 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
  • 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
  • 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, 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.
  • 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." In Proceedings of FOCS 2005, pages 357-366. .ps 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
  • 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.

    • Approximation Algorithms for Deterministic Inventory Models

  • T. Carnes and D.B. Shmoys. Primal-Dual Schema for Capacitated Covering Problems, Proceedings of the 13th MPS Conference on Integer Programming and Combinatorial Optimization, 2008, 288-302. .pdf version
  • 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.
  • 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.

    • Approximation Algorithms for Facility Location Problems

  • 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.
  • R. Levi, D.B. Shmoys, and C. Swamy. "LP-based approximation algorithms for capacitated facility location," in Proceedings of the 10th MPS Conference on Integer Programming and Combinatorial Optimization}, 2004, 206-218. .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
  • 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
  • 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.

    • Algorithms for Sequencing and Scheduling Problems

  • 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, 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.

    • Other Selected Papers

  • H.-C. An, R.D. Kleinberg, D.B. Shmoys. "Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem." Proceedings of APPROX-RANDOM, 2010, 1-11.
  • 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]
  • 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.
  • 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.

    • Selected Survey Papers

  • 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.
  • 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. "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 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. "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
  • C. Swamy and D.B. Shmoys. "Approximation algorithms for 2-stage stochastic optimization problems." In Proceedings in FSTTCS 2006, 5-19. .pdf file.

    • Forthcoming Book

  • D.P. Williamson and D.B. Shmoys. The Design of Approximation Algorithms.. Cambridge University Press, 2011.

    • Vita

    Current Courses

    Research

    Books

    Publications

    Current and Former PhD Students

    Shmoys Home

    Back to ORIE