Powers of Graphs: A Powerful Approximation Technique for Bottleneck Problems - Dorit S. Hochbaum; David B. Shmoys (STOC, 1984)

Recognizing graphs with fixed interval number is NP-complete. - Douglas B. West; David B. Shmoys (Discret. Appl. Math., 1984)

Simple Constant-Time Consensus Protocols in Realistic Failure Models (Extended Abstract). - Benny Chor; Michael Merritt; David B. Shmoys (PODC, 1985)

A Best Possible Heuristic for the k-Center Problem. - Dorit S. Hochbaum; David B. Shmoys (Math. Oper. Res., 1985)

Flipping Persuasively in Constant Expected Time (Preliminary Version) - Cynthia Dwork; David B. Shmoys; Larry J. Stockmeyer (FOCS, 1986)

A Polynomial Approximation Scheme for Machine Scheduling on Uniform Processors: Using the Dual Approximation Approach. - Dorit S. Hochbaum; David B. Shmoys (FSTTCS, 1986)

A unified approach to approximation algorithms for bottleneck problems. - Dorit S. Hochbaum; David B. Shmoys (J. ACM, 1986)

A Better than "Best Possible" Algorithm to Edge Color Multigraphs. - Dorit S. Hochbaum; Takao Nishizeki; David B. Shmoys (J. Algorithms, 1986)

Using dual approximation algorithms for scheduling problems theoretical and practical results. - Dorit S. Hochbaum; David B. Shmoys (J. ACM, 1987)

Efficient Parallel Algorithms for Edge Coloring Problems. - Howard J. Karloff; David B. Shmoys (J. Algorithms, 1987)

A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach. - Dorit S. Hochbaum; David B. Shmoys (SIAM J. Comput., 1988)

Interior-Point Methods in Parallel Computation - Andrew V. Goldberg; Serge A. Plotkin; David B. Shmoys; Éva Tardos (FOCS, 1989)

Approximation Schemes for Constrained Scheduling Problems - Leslie A. Hall; David B. Shmoys (FOCS, 1989)

Simple constant-time consensus protocols in realistic failure models. - Benny Chor; Michael Merritt; David B. Shmoys (J. ACM, 1989)

The Parallel Complexity of TSP Heuristics. - Gerard A. P. Kindervater; Jan Karel Lenstra; David B. Shmoys (J. Algorithms, 1989)

Near-Optimal Sequencing with Precedence Constraints. - Leslie A. Hall; David B. Shmoys (IPCO, 1990)

Analyzing the Held-Karp TSP Bound: A Monotonicity Property with Application. - David B. Shmoys; David P. Williamson (Inf. Process. Lett., 1990)

Approximation Algorithms for Scheduling Unrelated Parallel Machines. - Jan Karel Lenstra; David B. Shmoys; Éva Tardos (Math. Program., 1990)

Flipping Persuasively in Constant Time. - Cynthia Dwork; David B. Shmoys; Larry J. Stockmeyer (SIAM J. Comput., 1990)

Permutation vs. non-permutation flow shop schedules. - Chris N. Potts; David B. Shmoys; David P. Williamson (Oper. Res. Lett., 1991)

Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better. - Leslie A. Hall; David B. Shmoys (Math. Oper. Res., 1992)

Using Interior-Point Methods for Fast Parallel Algorithms for Bipartite Matching and Related Problems. - Andrew V. Goldberg; Serge A. Plotkin; David B. Shmoys; Éva Tardos (SIAM J. Comput., 1992)

Chapter 9 Sequencing and scheduling: Algorithms and complexity. - Eugene L. Lawler; Jan Karel Lenstra; Alexander H. G. Rinnooy Kan; David B. Shmoys (Logistics of Production and Inventory, 1993)

Computing near-optimal solutions to combinatorial optimization problems. - David B. Shmoys (Combinatorial Optimization, 1993)

Scheduling Unrelated Machines with Costs. - David B. Shmoys; Éva Tardos (SODA, 1993)

An approximation algorithm for the generalized assignment problem. - David B. Shmoys; Éva Tardos (Math. Program., 1993)

Improved Approximation Algorithms for Network Design Problems. - Michel X. Goemans; Andrew V. Goldberg; Serge A. Plotkin; David B. Shmoys; Éva Tardos; David P. Williamson (SODA, 1994)

Improved Approximation Algorithms for Shop Scheduling Problems. - David B. Shmoys; Clifford Stein 001; Joel Wein (SIAM J. Comput., 1994)

Fast Approximation Algorithms for Fractional Packing and Covering Problems. - Serge A. Plotkin; David B. Shmoys; Éva Tardos (Math. Oper. Res., 1995)

Scheduling Parallel Machines On-Line. - David B. Shmoys; Joel Wein; David P. Williamson (SIAM J. Comput., 1995)

Improved Scheduling Algorithms for Minsum Criteria. - Soumen Chakrabarti; Cynthia A. Phillips; Andreas S. Schulz; David B. Shmoys; Clifford Stein 001; Joel Wein (ICALP, 1996)

A New Approach to Computing Optimal Schedules for the Job-Shop Scheduling Problem. - Paul Martin 004; David B. Shmoys (IPCO, 1996)

Scheduling to Minimize Average Completion Time: Off-line and On-line Algorithms. - Leslie A. Hall; David B. Shmoys; Joel Wein (SODA, 1996)

Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines That Run at Fifferent Speeds (Extended Abstract). - Fabián A. Chudak; David B. Shmoys (SODA, 1997)

Approximation Algorithms for Facility Location Problems (Extended Abstract). - David B. Shmoys; Éva Tardos; Karen I. Aardal (STOC, 1997)

Short Shop Schedules. - David P. Williamson; Leslie A. Hall; J. A. Hoogeveen; Cor A. J. Hurkens; Jan Karel Lenstra; Sergey Vasil'evich Sevast'janov; David B. Shmoys (Oper. Res., 1997)

Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms. - Leslie A. Hall; Andreas S. Schulz; David B. Shmoys; Joel Wein (Math. Oper. Res., 1997)

Strategic directions in research in theory of computing. - Anne Condon; Faith E. Fich; Greg N. Frederickson; Andrew V. Goldberg; David S. Johnson 001; Michael C. Loui; Steven Mahaney; Prabhakar Raghavan; John E. Savage; Alan L. Selman; David B. Shmoys (SIGACT News, 1997)

Using Linear Programming in the Design and Analysis of Approximation Algorithms: Two Illustrative Problems. - David B. Shmoys (APPROX, 1998)

Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem. - Cynthia A. Phillips; Andreas S. Schulz; David B. Shmoys; Clifford Stein 001; Joel Wein (J. Comb. Optim., 1998)

Approximation Algorithms for Clustering Problems. - David B. Shmoys (COLT, 1999)

Improved Approximation Algorithms for a Capacitated Facility Location Problem. - Fabián A. Chudak; David B. Shmoys (SODA, 1999)

A Constant-Factor Approximation Algorithm for the k-Median Problem (Extended Abstract). - Moses Charikar; Sudipto Guha; Éva Tardos; David B. Shmoys (STOC, 1999)

A 3-Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem. - Karen I. Aardal; Fabián A. Chudak; David B. Shmoys (Inf. Process. Lett., 1999)

Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds. - Fabián A. Chudak; David B. Shmoys (J. Algorithms, 1999)

Approximation algorithms for facility location problems. - David B. Shmoys (APPROX, 2000)

A Constant-Factor Approximation Algorithm for the k-Median Problem. - Moses Charikar; Sudipto Guha; Éva Tardos; David B. Shmoys (J. Comput. Syst. Sci., 2002)

Lagrangian Relaxation for the k-Median Problem: New Insights and Continuity Properties. - Aaron Archer; Ranjithkumar Rajagopalan; David B. Shmoys (ESA, 2003)

Improved Approximation Algorithms for the Uncapacitated Facility Location Problem. - Fabián A. Chudak; David B. Shmoys (SIAM J. Comput., 2003)

Stochastic Optimization is (Almost) as easy as Deterministic Optimization. - David B. Shmoys; Chaitanya Swamy (FOCS, 2004)

Facility location with Service Installation Costs. - David B. Shmoys; Chaitanya Swamy; Retsef Levi (SODA, 2004)

Approximations and Randomization to Boost CSP Techniques. - Carla P. Gomes; David B. Shmoys (Ann. Oper. Res., 2004)

Foreword. - David B. Shmoys (J. Algorithms, 2004)

An improved approximation algorithm for the partial Latin square extension problem. - Carla P. Gomes; Rommel G. Regis; David B. Shmoys (Oper. Res. Lett., 2004)

Approximation Algorithms for 2-stage and Multi-stage Stochastic Optimization. - Chaitanya Swamy; David B. Shmoys (Algorithms for Optimization with Incomplete Information, 2005)

Sampling-based Approximation Algorithms for Multi-stage Stochastic. - Chaitanya Swamy; David B. Shmoys (FOCS, 2005)

Inventory and Facility Location Models with Market Selection. - Retsef Levi; Joseph Geunes; H. Edwin Romeijn; David B. Shmoys (IPCO, 2005)

A constant approximation algorithm for the one-warehouse multi-retailer problem. - Retsef Levi; Robin Roundy; David B. Shmoys (SODA, 2005)

The MSOM Society Student Paper Competition: Extended Abstracts of 2004 Winners. - Retsef Levi; Martin Pál; Robin O. Roundy; David B. Shmoys; Ravi Subramanian; Xinxin Hu; Gad Allon; Felipe Caro; Holly S. Lutze (Manuf. Serv. Oper. Manag., 2005)

Provably near-optimal sampling-based algorithms for Stochastic inventory control models. - Retsef Levi; Robin Roundy; David B. Shmoys (STOC, 2006)

An approximation scheme for stochastic linear programming and its application to stochastic integer programs. - David B. Shmoys; Chaitanya Swamy (J. ACM, 2006)

Primal-Dual Algorithms for Deterministic Inventory Problems. - Retsef Levi; Robin Roundy; David B. Shmoys (Math. Oper. Res., 2006)

Approximation algorithms for 2-stage stochastic optimization problems. - Chaitanya Swamy; David B. Shmoys (SIGACT News, 2006)

Sampling-based Approximation Algorithms for Multi-stage Stochastic Optimization. - Chaitanya Swamy; David B. Shmoys (Probabilistic Methods in the Design and Analysis of Algorithms, 2007)

Approximation Algorithms for 2-Stage Stochastic Scheduling Problems. - David B. Shmoys; Mauro Sozio (IPCO, 2007)

Approximation Algorithms for Stochastic Inventory Control Models. - Retsef Levi; Martin Pál; Robin Roundy; David B. Shmoys (Math. Oper. Res., 2007)

Provably Near-Optimal Sampling-Based Policies for Stochastic Inventory Control Models. - Retsef Levi; Robin Roundy; David B. Shmoys (Math. Oper. Res., 2007)

A Constant Approximation Algorithm for the a prioriTraveling Salesman Problem. - David B. Shmoys; Kunal Talwar (IPCO, 2008)

Approximation Algorithms for Capacitated Stochastic Inventory Control Models. - Retsef Levi; Robin Roundy; David B. Shmoys; Van-Anh Truong (Oper. Res., 2008)

A Constant Approximation Algorithm for the One-Warehouse Multiretailer Problem. - Retsef Levi; Robin Roundy; David B. Shmoys; Maxim Sviridenko (Manag. Sci., 2008)

Algorithms for the universal and a priori TSP. - Frans Schalekamp; David B. Shmoys (Oper. Res. Lett., 2008)

Fault-tolerant facility location. - Chaitanya Swamy; David B. Shmoys (ACM Trans. Algorithms, 2008)

A PTAS for capacitated sum-of-ratios optimization. - Paat Rusmevichientong; Zuo-Jun Max Shen; David B. Shmoys (Oper. Res. Lett., 2009)

Improved Lower Bounds for the Universal and a priori TSP. - Igor Gorodezky; Robert D. Kleinberg; David B. Shmoys; Gwen Spencer (APPROX-RANDOM, 2010)

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

Dynamic Assortment Optimization with a Multinomial Logit Choice Model and Capacity Constraint. - Paat Rusmevichientong; Zuo-Jun Max Shen; David B. Shmoys (Oper. Res., 2010)

The Design of Approximation Algorithms. - David P. Williamson; David B. Shmoys (Cambridge University Press, 2011)

Primal-Dual Schema and Lagrangian Relaxation for the k-Location-Routing Problem. - Tim Carnes; David B. Shmoys (APPROX-RANDOM, 2011)

A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems. - Maurice Cheung; David B. Shmoys (APPROX-RANDOM, 2011)

LP-Based Approximation Algorithms for Traveling Salesman Path Problems - Hyung-Chan An; David B. Shmoys (CoRR, 2011)

Approximation algorithms for supply chain planning and logistics problems with market choice. - Joseph Geunes; Retsef Levi; H. Edwin Romeijn; David B. Shmoys (Math. Program., 2011)

LP-based approximation algorithms for capacitated facility location. - Retsef Levi; David B. Shmoys; Chaitanya Swamy (Math. Program., 2012)

Sampling-Based Approximation Algorithms for Multistage Stochastic Optimization. - Chaitanya Swamy; David B. Shmoys (SIAM J. Comput., 2012)

Mathematical Programming Guides Air-Ambulance Routing at Ornge. - Timothy A. Carnes; Shane G. Henderson; David B. Shmoys; Mahvareh Ahghari; Russell D. MacDonald (Interfaces, 2013)

Data Analysis and Optimization for (Citi)Bike Sharing. - Eoin O'Mahony; David B. Shmoys (AAAI, 2015)

Predicting Bike Usage for New York City's Bike Sharing System. - Divya Singhvi; Somya Singhvi; Peter I. Frazier; Shane G. Henderson; Eoin O'Mahony; David B. Shmoys; Dawn B. Woodard (AAAI Workshop: Computational Sustainability, 2015)

Improving Christofides' Algorithm for the s-t Path TSP. - Hyung-Chan An; Robert D. Kleinberg; David B. Shmoys (J. ACM, 2015)

Primal-dual schema for capacitated covering problems. - Tim Carnes; David B. Shmoys (Math. Program., 2015)

Approximation Algorithms for Fragmenting a Graph Against a Stochastically-Located Threat. - David B. Shmoys; Gwen Spencer (Theory Comput. Syst., 2015)

The submodular joint replenishment problem. - Maurice Cheung; Adam N. Elmachtoub; Retsef Levi; David B. Shmoys (Math. Program., 2016)

Prize-Collecting TSP with a Budget Constraint. - Alice Paul; Daniel Freund 001; Aaron M. Ferber; David B. Shmoys; David P. Williamson (ESA, 2017)

A Bicriteria Approximation Algorithm for the k-Center and k-Median Problems. - Soroush Alamdari; David B. Shmoys (WAOA, 2017)

A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems. - Maurice Cheung; Julián Mestre; David B. Shmoys; José Verschae (SIAM J. Discret. Math., 2017)

Bike Angels: An Analysis of Citi Bike's Incentive Program. - Hangil Chung; Daniel Freund 001; David B. Shmoys (COMPASS, 2018)

Sincronia: near-optimal network design for coflows. - Saksham Agarwal; Shijin Rajakrishnan; Akshay Narayan 001; Rachit Agarwal 001; David B. Shmoys; Amin Vahdat (SIGCOMM, 2018)

Computational sustainability: computing for a better world and a sustainable future. - Carla P. Gomes; Thomas G. Dietterich; Christopher Barrett; Jon Conrad; Bistra Dilkina; Stefano Ermon; Fei Fang 001; Andrew Farnsworth; Alan Fern; Xiaoli Z. Fern; Daniel Fink 002; Douglas H. Fisher; et al. (Commun. ACM, 2019)

Analytics and Bikes: Riding Tandem with Motivate to Improve Mobility. - Daniel Freund 001; Shane G. Henderson; Eoin O'Mahony; David B. Shmoys (INFORMS J. Appl. Anal., 2019)

Elements of Scheduling. - Jan Karel Lenstra; David B. Shmoys (CoRR, 2020)

Scheduling (Dagstuhl Seminar 20081). - Nicole Megow; David B. Shmoys; Ola Svensson (Dagstuhl Reports, 2020)

Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems. - Alice Paul; Daniel Freund 001; Aaron M. Ferber; David B. Shmoys; David P. Williamson (Math. Oper. Res., 2020)

Fairmandering: A column generation heuristic for fairness-optimized political districting. - Wes Gurnee; David B. Shmoys (ACDA, 2021)

On the Power of Static Assignment Policies for Robust Facility Location Problems. - Omar El Housni; Vineet Goyal; David B. Shmoys (IPCO, 2021)

Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem. - Hyung-Chan An; Robert Kleinberg; David B. Shmoys (ACM Trans. Algorithms, 2021)

From Switch Scheduling to Datacenter Scheduling: Matching-Coordinated Greed is Good. - Rachit Agarwal 001; Shijin Rajakrishnan; David B. Shmoys (PODC, 2022)

Combatting Gerrymandering with Social Choice: The Design of Multi-member Districts. - Nikhil Garg 001; Wes Gurnee; David Rothschild; David B. Shmoys (EC, 2022)

Scheduling Appointments Online: The Power of Deferred Decision-Making. - Devin Smedira; David B. Shmoys (WAOA, 2022)

GILP: An Interactive Tool for Visualizing the Simplex Algorithm. - Henry W. Robbins; Samuel C. Gutekunst; Frans Schalekamp; David B. Shmoys; David P. Williamson (CoRR, 2022)

Scheduling with Predictions. - Woo-Hyung Cho; Shane G. Henderson; David B. Shmoys (CoRR, 2022)

Minimizing Multimodular Functions and Allocating Capacity in Bike-Sharing Systems. - Daniel Freund 001; Shane G. Henderson; David B. Shmoys (Oper. Res., 2022)

GILP: An Interactive Tool for Visualizing the Simplex Algorithm. - Henry W. Robbins; Samuel C. Gutekunst; David B. Shmoys; David P. Williamson (SIGCSE (1), 2023)

Hitting Sets when the Shallow Cell Complexity is Small. - Sander Aarts; David B. Shmoys (WAOA, 2023)

An Interpretable Determinantal Choice Model for Subset Selection. - Sander Aarts; David B. Shmoys; Alex Coy (CoRR, 2023)

Sharing the Cost of IoT Wireless Coverage with a Strengthened Linear Programming Formulation. - Sander Aarts; Manxi Wu; David B. Shmoys (CoRR, 2023)

Erratum to "Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems". - Alice Paul; Daniel Freund 001; Aaron M. Ferber; David B. Shmoys; David P. Williamson (Math. Oper. Res., 2023)

SPT optimality (mostly) via linear programming. - Woo-Hyung Cho; David B. Shmoys; Shane G. Henderson (Oper. Res. Lett., 2023)

Scheduling (Dagstuhl Seminar 23061). - Nicole Megow; Benjamin Moseley; David B. Shmoys; Ola Svensson; Sergei Vassilvitskii; Jens Schlöter (Dagstuhl Reports, 2023)

A min-max theorem for the minimum fleet-size problem. - Tinghan Ye; David B. Shmoys (Oper. Res. Lett., 2023)

Network Flow Problems with Electric Vehicles. - Haripriya Pulyassary; Kostas Kollias; Aaron Schild; David B. Shmoys; Manxi Wu (IPCO, 2024)

Harmony: A Congestion-free Datacenter Architecture. - Saksham Agarwal; Qizhe Cai; Rachit Agarwal 001; David B. Shmoys; Amin Vahdat (NSDI, 2024)

Improved Approximation Algorithms for the Joint Replenishment Problem with Outliers, and with Fairness Constraints. - Varun Suriyanarayana; Varun Sivashankar; Siddharth Gollapudi; David B. Shmoys (SODA, 2024)

Bounding the Price-of-Fair-Sharing Using Knapsack-Cover Constraints to Guide Near-Optimal Cost-Recovery Algorithms. - Sander Aarts; Jacob Dentes; Manxi Wu; David B. Shmoys (WAOA, 2024)

Small Additive Error for Unsplittable Multicommodity Flow in Outerplanar Graphs. - Richard Shapley; David B. Shmoys (WAOA, 2024)

A Data-Driven Model for LoRaWAN Connection Quality and Coverage. - Rodriguez Alfredo; Sander Aarts; Ali Amadeh; Jacob Dentes; Alex Coy; Kenneth Schlather; David B. Shmoys; K. Max Zhang (WF-IoT, 2024)

Modeling the Risk of In-Person Instruction During the COVID-19 Pandemic. - Brian Liu 002; Yujia Zhang; Shane G. Henderson; David B. Shmoys; Peter I. Frazier (INFORMS J. Appl. Anal., 2024)

Reducing Income Variability in Natural Resource Portfolios via Integer Programming. - Laura Greenstreet; Qinru Shi; Marc Grimson; Franz W. Simon; Suresh Andrew Sethi; Carla P. Gomes; Andrea Lodi 001; David B. Shmoys (CPAIOR (2), 2025)