Select a publication 
Show 
Title 
Venue 
Rating 
Date 

Conference paper
Tim Carnes, Shane G. Henderson, David B. Shmoys, Mahvareh Ahghari, Russell D. MacDonald.
Mathematical Programming Guides AirAmbulance Routing at Ornge.

Interfaces 2013, Volume 43 
(0)

2013 

Journal article
Retsef Levi, David B. Shmoys, Chaitanya Swamy.
LPbased approximation algorithms for capacitated facility location.

Math. Program. 2012, Volume 131 
(0)

2012 

Conference paper
HyungChan An, Robert D. Kleinberg, David B. Shmoys.
Improving christofides' algorithm for the st path TSP.

Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19  22, 2012 2012 
(0)

2012 

Conference paper
Daniel Sheldon, Bistra N. Dilkina, Adam N. Elmachtoub, Ryan Finseth, Ashish Sabharwal, Jon Conrad, Carla P. Gomes, David B. Shmoys, William Allen, Ole Amundsen, William Vaughan.
Maximizing the Spread of Cascades Using Network Design

CoRR 2012, Volume 0 
(0)

2012 

Conference paper
Chaitanya Swamy, David B. Shmoys.
SamplingBased Approximation Algorithms for Multistage Stochastic Optimization.

SIAM J. Comput. 2012, Volume 41 
(0)

2012 

Journal article
HyungChan An, David B. Shmoys.
LPBased Approximation Algorithms for Traveling Salesman Path Problems

CoRR 2011, Volume 0 
(0)

2011 

Conference paper
Tim Carnes, David B. Shmoys.
PrimalDual Schema and Lagrangian Relaxation for the kLocationRouting Problem.

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques  14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 1719, 2011. Proceedings 2011 
(0)

2011 

Conference paper
Maurice Cheung, David B. Shmoys.
A PrimalDual Approximation Algorithm for MinSum SingleMachine Scheduling Problems.

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques  14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 1719, 2011. Proceedings 2011 
(0)

2011 

Journal article
Joseph Geunes, Retsef Levi, H. Edwin Romeijn, David B. Shmoys.
Approximation algorithms for supply chain planning and logistics problems with market choice.

Math. Program. 2011, Volume 130 
(0)

2011 

Conference paper
HyungChan An, Robert D. Kleinberg, David B. Shmoys.
Improving Christofides' Algorithm for the st Path TSP

CoRR 2011, Volume 0 
(0)

2011 

Conference paper
David B. Shmoys, Gwen Spencer.
Approximation Algorithms for Fragmenting a Graph against a StochasticallyLocated Threat.

Approximation and Online Algorithms  9th International Workshop, WAOA 2011, Saarbrücken, Germany, September 89, 2011, Revised Selected Papers 2012 
(0)

2011 

Conference paper
Igor Gorodezky, Robert D. Kleinberg, David B. Shmoys, Gwen Spencer.
Improved Lower Bounds for the Universal and

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 13, 2010. Proceedings 2010 
(0)

2010 

Conference paper
Robert D. Kleinberg, David B. Shmoys.
Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem.

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 13, 2010. Proceedings 2010 
(0)

2010 

Conference paper
Paat Rusmevichientong, ZuoJun Max Shen, David B. Shmoys.
Dynamic Assortment Optimization with a Multinomial Logit Choice Model and Capacity Constraint.

Operations Research 2010, Volume 58 
(0)

2010 

Conference paper
Daniel Sheldon, Bistra N. Dilkina, Adam N. Elmachtoub, Ryan Finseth, Ashish Sabharwal, Jon Conrad, Carla P. Gomes, David B. Shmoys, William Allen, Ole Amundsen, William Vaughan.
Maximizing the Spread of Cascades Using Network Design.

UAI 2010, Proceedings of the TwentySixth Conference on Uncertainty in Artificial Intelligence, Catalina Island, CA, USA, July 811, 2010 2010 
(0)

2010 

Conference paper
Paat Rusmevichientong, ZuoJun Max Shen, David B. Shmoys.
A PTAS for capacitated sumofratios optimization.

Oper. Res. Lett. 2009, Volume 37 
(0)

2009 

Conference paper
Tim Carnes, David B. Shmoys.
PrimalDual Schema for Capacitated Covering Problems.

Integer Programming and Combinatorial Optimization, 13th International Conference, IPCO 2008, Bertinoro, Italy, May 2628, 2008, Proceedings 2008 
(0)

2008 

Conference paper
David B. Shmoys, Kunal Talwar.
A Constant Approximation Algorithm for the a prioriTraveling Salesman Problem.

Integer Programming and Combinatorial Optimization, 13th International Conference, IPCO 2008, Bertinoro, Italy, May 2628, 2008, Proceedings 2008 
(0)

2008 

Conference paper
Frans Schalekamp, David B. Shmoys.
Algorithms for the universal and a priori TSP.

Oper. Res. Lett. 2008, Volume 36 
(0)

2008 

Conference paper
Chaitanya Swamy, David B. Shmoys.
Faulttolerant facility location.

ACM Transactions on Algorithms 2008, Volume 4 
(0)

2008 

Conference paper
Retsef Levi, Robin Roundy, David B. Shmoys, Van Anh Truong.
Approximation Algorithms for Capacitated Stochastic Inventory Control Models.

Operations Research 2008, Volume 56 
(0)

2008 

Journal article
Retsef Levi, Robin Roundy, David B. Shmoys, Maxim Sviridenko.
A Constant Approximation Algorithm for the OneWarehouse Multiretailer Problem.

Management Science 2008, Volume 54 
(0)

2008 

Conference paper
Chaitanya Swamy, David B. Shmoys.
Samplingbased Approximation Algorithms for Multistage Stochastic Optimization.

Probabilistic Methods in the Design and Analysis of Algorithms, 23.09.  28.09.2007 2007 
(0)

2007 

Conference paper
David B. Shmoys, Mauro Sozio.
Approximation Algorithms for 2Stage Stochastic Scheduling Problems.

Integer Programming and Combinatorial Optimization, 12th International IPCO Conference, Ithaca, NY, USA, June 2527, 2007, Proceedings 2007 
(0)

2007 

Conference paper
Retsef Levi, Martin Pál, Robin Roundy, David B. Shmoys.
Approximation Algorithms for Stochastic Inventory Control Models.

Math. Oper. Res. 2007, Volume 32 
(0)

2007 

Conference paper
Retsef Levi, Robin Roundy, David B. Shmoys.
Provably NearOptimal SamplingBased Policies for Stochastic Inventory Control Models.

Math. Oper. Res. 2007, Volume 32 
(0)

2007 

Conference paper
Chaitanya Swamy, David B. Shmoys.
Approximation Algorithms for 2Stage Stochastic Optimization Problems.

FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 26th International Conference, Kolkata, India, December 1315, 2006, Proceedings 2006 
(0)

2006 

Conference paper
Retsef Levi, Robin Roundy, David B. Shmoys.
Provably nearoptimal samplingbased algorithms for Stochastic inventory control models.

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 2123, 2006 2006 
(0)

2006 

Conference paper
David B. Shmoys, Chaitanya Swamy.
An approximation scheme for stochastic linear programming and its application to stochastic integer programs.

J. ACM 2006, Volume 53 
(0)

2006 

Conference paper
Retsef Levi, Robin Roundy, David B. Shmoys.
PrimalDual Algorithms for Deterministic Inventory Problems.

Math. Oper. Res. 2006, Volume 31 
(0)

2006 

Conference paper
Chaitanya Swamy, David B. Shmoys.
Approximation algorithms for 2stage stochastic optimization problems.

SIGACT News 2006, Volume 37 
(0)

2006 

Conference paper
Chaitanya Swamy, David B. Shmoys.
Approximation Algorithms for 2stage and Multistage Stochastic Optimization.

Algorithms for Optimization with Incomplete Information, 16.21. January 2005 2005 
(0)

2005 

Conference paper
Chaitanya Swamy, David B. Shmoys.
Samplingbased Approximation Algorithms for Multistage Stochastic.

46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2325 October 2005, Pittsburgh, PA, USA, Proceedings 2005 
(0)

2005 

Conference paper
Retsef Levi, Joseph Geunes, H. Edwin Romeijn, David B. Shmoys.
Inventory and Facility Location Models with Market Selection.

Integer Programming and Combinatorial Optimization, 11th International IPCO Conference, Berlin, Germany, June 810, 2005, Proceedings 2005 
(0)

2005 

Conference paper
Retsef Levi, Martin Pál, Robin Roundy, David B. Shmoys.
Approximation Algorithms for Stochastic Inventory Control Models.

Integer Programming and Combinatorial Optimization, 11th International IPCO Conference, Berlin, Germany, June 810, 2005, Proceedings 2005 
(0)

2005 

Conference paper
Retsef Levi, Robin Roundy, David B. Shmoys.
A constant approximation algorithm for the onewarehouse multiretailer problem.

Proceedings of the Sixteenth Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 2325, 2005 2005 
(0)

2005 

Conference paper
David B. Shmoys, Chaitanya Swamy.
Stochastic Optimization is (Almost) as easy as Deterministic Optimization.

45th Symposium on Foundations of Computer Science (FOCS 2004), 1719 October 2004, Rome, Italy, Proceedings 2004 
(0)

2004 

Conference paper
Retsef Levi, David B. Shmoys, Chaitanya Swamy.
LPbased Approximation Algorithms for Capacitated Facility Location.

Integer Programming and Combinatorial Optimization, 10th International IPCO Conference, New York, NY, USA, June 711, 2004, Proceedings 2004 
(0)

2004 

Conference paper
David B. Shmoys, Chaitanya Swamy, Retsef Levi.
Facility location with Service Installation Costs.

Proceedings of the Fifteenth Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 1114, 2004 2004 
(0)

2004 

Conference paper
Retsef Levi, Robin Roundy, David B. Shmoys.
Primaldual algorithms for deterministic inventory problems.

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 1316, 2004 2004 
(0)

2004 

Conference paper
David B. Shmoys.
Foreword.

J. Algorithms 2004, Volume 50 
(0)

2004 

Conference paper
Carla P. Gomes, Rommel G. Regis, David B. Shmoys.
An improved approximation algorithm for the partial Latin square extension problem.

Oper. Res. Lett. 2004, Volume 32 
(0)

2004 

Conference paper
Carla P. Gomes, David B. Shmoys.
Approximations and Randomization to Boost CSP Techniques.

Annals OR 2004, Volume 130 
(0)

2004 

Conference paper
Aaron Archer, Ranjithkumar Rajagopalan, David B. Shmoys.
Lagrangian Relaxation for the kMedian Problem: New Insights and Continuity Properties.

Algorithms  ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 1619, 2003, Proceedings 2003 
(0)

2003 

Conference paper
Carla P. Gomes, Rommel G. Regis, David B. Shmoys.
An improved approximation algorithm for the partial latin square extension problem.

SODA 2003 
(0)

2003 

Conference paper
Chaitanya Swamy, David B. Shmoys.
Faulttolerant facility location.

SODA 2003 
(0)

2003 

Conference paper
Fabián A. Chudak, David B. Shmoys.
Improved Approximation Algorithms for the Uncapacitated Facility Location Problem.

SIAM J. Comput. 2004, Volume 33 
(0)

2003 

Conference paper
Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys.
A ConstantFactor Approximation Algorithm for the kMedian Problem.

J. Comput. Syst. Sci. 2002, Volume 65 
(0)

2002 

Conference paper
David B. Shmoys.
Approximation algorithms for facility location problems.

Approximation Algorithms for Combinatorial Optimization, Third International Workshop, APPROX 2000, Saarbrücken, Germany, September 58, 2000, Proceedings 2000 
(0)

2000 

Conference paper
David B. Shmoys.
Approximation Algorithms for Clustering Problems.

COLT 1999 
(0)

1999 

Conference paper
Fabián A. Chudak, David B. Shmoys.
Improved Approximation Algorithms for a Capacitated Facility Location Problem.

SODA 1999 
(0)

1999 

Conference paper
Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys.
A ConstantFactor Approximation Algorithm for the

STOC 1999 
(0)

1999 

Conference paper
Karen Aardal, Fabián A. Chudak, David B. Shmoys.
A 3Approximation Algorithm for the kLevel Uncapacitated Facility Location Problem.

Inf. Process. Lett. 1999, Volume 72 
(0)

1999 

Conference paper
Fabián A. Chudak, David B. Shmoys.
Approximation Algorithms for PrecedenceConstrained Scheduling Problems on Parallel Machines that Run at Different Speeds.

J. Algorithms 1999, Volume 30 
(0)

1999 

Conference paper
David B. Shmoys.
Using Linear Programming in the Design and Analysis of Approximation Algorithms: Two Illustrative Problems.

Approximation Algorithms for Combinatorial Optimization, International Workshop APPROX'98, Aalborg, Denmark, July 1819, 1998, Proceedings 1998 
(0)

1998 

Conference paper
Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Clifford Stein, Joel Wein.
Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem.

J. Comb. Optim. 1998, Volume 1 
(0)

1998 

Conference paper
David B. Shmoys, Éva Tardos, Karen Aardal.
Approximation Algorithms for Facility Location Problems (Extended Abstract).

STOC 1997 
(0)

1997 

Conference paper
Fabián A. Chudak, David B. Shmoys.
Approximation Algorithms for PrecedenceConstrained Scheduling Problems on Parallel Machines That Run at Fifferent Speeds (Extended Abstract).

SODA 1997 
(0)

1997 

Journal article
Anne Condon, Faith Fich, Greg N. Frederickson, Andrew V. Goldberg, David S. Johnson, Michael C. Loui, Steven Mahaney, Prabhakar Raghavan, John E. Savage, Alan L. Selman, David B. Shmoys.
Strategic directions in research in theory of computing.

SIGACT News 1997, Volume 28 
(0)

1997 

Conference paper
Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Clifford Stein, Joel Wein.
Improved Scheduling Algorithms for Minsum Criteria.

Automata, Languages and Programming, 23rd International Colloquium, ICALP96, Paderborn, Germany, 812 July 1996, Proceedings 1996 
(0)

1996 

Conference paper
Paul Martin, David B. Shmoys.
A New Approach to Computing Optimal Schedules for the JobShop Scheduling Problem.

Integer Programming and Combinatorial Optimization, 5th International IPCO Conference, Vancouver, British Columbia, Canada, June 35, 1996, Proceedings 1996 
(0)

1996 

Conference paper
Leslie A. Hall, David B. Shmoys, Joel Wein.
Scheduling to Minimize Average Completion Time: Offline and Online Algorithms.

SODA 1996 
(0)

1996 

Conference paper
David B. Shmoys, Joel Wein, David P. Williamson.
Scheduling Parallel Machines OnLine.

SIAM J. Comput. 1995, Volume 24 
(0)

1995 

Conference paper
David B. Shmoys, Clifford Stein, Joel Wein.
Improved Approximation Algorithms for Shop Scheduling Problems.

SIAM J. Comput. 1994, Volume 23 
(0)

1994 

Conference paper
Michel X. Goemans, Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos, David P. Williamson.
Improved Approximation Algorithms for Network Design Problems.

SODA 1994 
(0)

1994 

Conference paper
David B. Shmoys, Éva Tardos.
An approximation algorithm for the generalized assignment problem.

Math. Program. 1993, Volume 62 
(0)

1993 

Conference paper
David B. Shmoys, Éva Tardos.
Scheduling Unrelated Machines with Costs.

SODA 1993 
(0)

1993 

Conference paper
Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos.
Using InteriorPoint Methods for Fast Parallel Algorithms for Bipartite Matching and Related Problems.

SIAM J. Comput. 1992, Volume 21 
(0)

1992 

Conference paper
Serge A. Plotkin, David B. Shmoys, Éva Tardos.
Fast Approximation Algorithms for Fractional Packing and Covering Problems

32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 14 October 1991 1991 
(0)

1991 

Conference paper
David B. Shmoys, Joel Wein, David P. Williamson.
Scheduling Parallel Machines OnLine

32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 14 October 1991 1991 
(0)

1991 

Conference paper
David B. Shmoys, Clifford Stein, Joel Wein.
Improved Approximation Algorithms for Shop Scheduling Problems.

SODA 1991 
(0)

1991 

Conference paper
Leslie A. Hall, David B. Shmoys.
NearOptimal Sequencing with Precedence Constraints.

Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, Waterloo, Ontorio, Canada, May 2830 1990 1990 
(0)

1990 

Conference paper
David B. Shmoys, David P. Williamson.
Analyzing the HeldKarp TSP Bound: A Monotonicity Property with Application.

Inf. Process. Lett. 1990, Volume 35 
(0)

1990 

Conference paper
Jan Karel Lenstra, David B. Shmoys, Éva Tardos.
Approximation Algorithms for Scheduling Unrelated Parallel Machines.

Math. Program. 1990, Volume 46 
(0)

1990 

Conference paper
Cynthia Dwork, David B. Shmoys, Larry J. Stockmeyer.
Flipping Persuasively in Constant Time.

SIAM J. Comput. 1990, Volume 19 
(0)

1990 

Conference paper
Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos.
InteriorPoint Methods in Parallel Computation

30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October  1 November 1989 1989 
(0)

1989 

Conference paper
Leslie A. Hall, David B. Shmoys.
Approximation Schemes for Constrained Scheduling Problems

30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October  1 November 1989 1989 
(0)

1989 

Conference paper
Benny Chor, Michael Merritt, David B. Shmoys.
Simple constanttime consensus protocols in realistic failure models.

J. ACM 1989, Volume 36 
(0)

1989 

Conference paper
Gerard A. P. Kindervater, Jan Karel Lenstra, David B. Shmoys.
The Parallel Complexity of TSP Heuristics.

J. Algorithms 1989, Volume 10 
(0)

1989 

Conference paper
Dorit S. Hochbaum, David B. Shmoys.
A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach.

SIAM J. Comput. 1988, Volume 17 
(0)

1988 

Conference paper
Jan Karel Lenstra, David B. Shmoys, Éva Tardos.
Approximation Algorithms for Scheduling Unrelated Parallel Machines

28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 2729 October 1987 1987 
(0)

1987 

Conference paper
Dorit S. Hochbaum, David B. Shmoys.
Using dual approximation algorithms for scheduling problems theoretical and practical results.

J. ACM 1987, Volume 34 
(0)

1987 

Conference paper
Howard J. Karloff, David B. Shmoys.
Efficient Parallel Algorithms for Edge Coloring Problems.

J. Algorithms 1987, Volume 8 
(0)

1987 

Conference paper
Cynthia Dwork, David B. Shmoys, Larry J. Stockmeyer.
Flipping Persuasively in Constant Expected Time (Preliminary Version)

27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 2729 October 1986 1986 
(0)

1986 

Conference paper
Dorit S. Hochbaum, David B. Shmoys.
A Polynomial Approximation Scheme for Machine Scheduling on Uniform Processors: Using the Dual Approximation Approach.

Foundations of Software Technology and Theoretical Computer Science, Sixth Conference, New Delhi, India, December 1820, 1986, Proceedings 1986 
(0)

1986 

Conference paper
Dorit S. Hochbaum, David B. Shmoys.
A unified approach to approximation algorithms for bottleneck problems.

J. ACM 1986, Volume 33 
(0)

1986 

Conference paper
Dorit S. Hochbaum, Takao Nishizeki, David B. Shmoys.
A Better than "Best Possible" Algorithm to Edge Color Multigraphs.

J. Algorithms 1986, Volume 7 
(0)

1986 

Conference paper
Dorit S. Hochbaum, David B. Shmoys.
Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results

26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 2123 October 1985 1985 
(0)

1985 

Conference paper
Benny Chor, Michael Merritt, David B. Shmoys.
Simple ConstantTime Consensus Protocols in Realistic Failure Models (Extended Abstract).

PODC 1985 
(0)

1985 

Conference paper
Dorit S. Hochbaum, David B. Shmoys.
Powers of Graphs: A Powerful Approximation Technique for Bottleneck Problems

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30  May 2, 1984, Washington, DC, USA 1984 
(0)

1984 