David B. Shmoys
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
David B. Shmoys has a total of 58 co-authors. Here are the top co-authors by number of shared publications:
- Shane G. Henderson
School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
9 shared publications - Peter I. Frazier
School of Operations Research & Information Engineering, Cornell University, Ithaca, New York 14850
5 shared publications - Haripriya Pulyassary
Cornell University
3 shared publications - Jiayue Wan
School of Operations Research & Information Engineering, Cornell University, Ithaca, New York 14850
3 shared publications - Kostas Kollias
Google Research, Mountain View, USA
3 shared publications - Manxi Wu
University of California Berkeley, Berkeley, CA, USA
3 shared publications
Latest Publications
- 1 November 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 74 (6) , 2937-2956
Combating Gerrymandering with Ranked Choice Voting: An Experimental Analysis of Multimember Districts in the United States
Blunting Gerrymandering with Multimember Districts How much can election rules blunt the power of partisan mapmakers? In the Operations Research paper “Combating Gerrymandering with Ranked Choice Voting: An Experimental Analysis of Multimember Districts in the United States,” Nikhil Garg, Wes Gurnee, David Rothschild, and David B. Shmoys study this question by combining computational redistricting with models of multiwinner voting. The authors compare single-member districts with multimember districts elected under rules such as single transferable vote (ranked choice voting), using algorithmically generated maps for the U.S. House of Representatives. Their results suggest that even modest three-member districts can help independent commissions reach proportional outcomes, sharply reducing the range of outcomes available to partisan gerrymanderers. The study also tests robustness under voter crossover and explores trade-offs involving geographic cohesion and within-party diversity. The paper points to election-system design as an operations research problem with direct democratic consequences.
- 1 November 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 74 (6) , 2937-2956
Combating Gerrymandering with Ranked Choice Voting: An Experimental Analysis of Multimember Districts in the United States
Blunting Gerrymandering with Multimember Districts How much can election rules blunt the power of partisan mapmakers? In the Operations Research paper “Combating Gerrymandering with Ranked Choice Voting: An Experimental Analysis of Multimember Districts in the United States,” Nikhil Garg, Wes Gurnee, David Rothschild, and David B. Shmoys study this question by combining computational redistricting with models of multiwinner voting. The authors compare single-member districts with multimember districts elected under rules such as single transferable vote (ranked choice voting), using algorithmically generated maps for the U.S. House of Representatives. Their results suggest that even modest three-member districts can help independent commissions reach proportional outcomes, sharply reducing the range of outcomes available to partisan gerrymanderers. The study also tests robustness under voter crossover and explores trade-offs involving geographic cohesion and within-party diversity. The paper points to election-system design as an operations research problem with direct democratic consequences.
- Open Access
- 11 August 2026
- Published by Association for Computing Machinery (ACM)
- p. 177-189
OptCCL: Scalable Synthesis of Optimal Collective Communication Algorithms
We present OptCCL, a technique to synthesize collective communication algorithms that are optimal for a given host and network hardware and topology. OptCCL is general: it enables synthesizing optimal algorithms for all existing collectives, for all existing hardware, and even for multiple concurrent collectives sharing host and network resources. And yet, OptCCL is scalable: it synthesizes optimal algorithms for hundreds of GPUs within tens of minutes.
- 11 August 2026
- Published by Association for Computing Machinery (ACM)
- p. 177-189
Open AccessOptCCL: Scalable Synthesis of Optimal Collective Communication Algorithms
We present OptCCL, a technique to synthesize collective communication algorithms that are optimal for a given host and network hardware and topology. OptCCL is general: it enables synthesizing optimal algorithms for all existing collectives, for all existing hardware, and even for multiple concurrent collectives sharing host and network resources. And yet, OptCCL is scalable: it synthesizes optimal algorithms for hundreds of GPUs within tens of minutes.
- Open Access
Improved Online Algorithms for Inventory Management Problems with Holding and Delay Costs: Riding the Wave Makes Things Simpler, Stronger, & More General
The Joint Replenishment Problem (JRP) is a classical inventory management problem, that aims to model the trade-off between coordinating orders for multiple commodities (and their cost) with holding costs incurred by meeting demand in advance. Moseley, Niaparast and Ravi introduced a natural online generalization of the JRP in which inventory corresponding to demands may be replenished late, for a delay cost, or early, for a holding cost. They established that when the holding and delay costs are monotone and uniform across demands, there is a 30-competitive algorithm that employs a greedy strategy and a dual-fitting based analysis. We develop a 5-competitive algorithm that handles arbitrary monotone demand-specific holding and delay cost functions, thus simultaneously improving upon the competitive ratio and relaxing the uniformity assumption. Our primal-dual algorithm is in the spirit of the work Buchbinder, Kimbrel, Levi, Makarychev, and Sviridenko, which maintains a wavefront dual solution to decide when to place an order and which items to order. The main twist is in deciding which requests to serve early. In contrast to the work of Moseley et al., which ranks early requests in ascending order of desired service time and serves them until their total holding cost matches the ordering cost incurred for that item, we extend to the non-uniform case by instead ranking in ascending order of when the delay cost of a demand would reach its current holding cost. An important special case of the JRP is the single-item lot-sizing problem. Here, Moseley et al. gave a 3-competitive algorithm when the holding and delay costs are uniform across demands. We provide a new algorithm for which the competitive ratio is $φ+1 \approx 2.681$, where $φ$ is the golden ratio, which again holds for arbitrary monotone holding-delay costs.Open AccessImproved Online Algorithms for Inventory Management Problems with Holding and Delay Costs: Riding the Wave Makes Things Simpler, Stronger, & More General
The Joint Replenishment Problem (JRP) is a classical inventory management problem, that aims to model the trade-off between coordinating orders for multiple commodities (and their cost) with holding costs incurred by meeting demand in advance. Moseley, Niaparast and Ravi introduced a natural online generalization of the JRP in which inventory corresponding to demands may be replenished late, for a delay cost, or early, for a holding cost. They established that when the holding and delay costs are monotone and uniform across demands, there is a 30-competitive algorithm that employs a greedy strategy and a dual-fitting based analysis. We develop a 5-competitive algorithm that handles arbitrary monotone demand-specific holding and delay cost functions, thus simultaneously improving upon the competitive ratio and relaxing the uniformity assumption. Our primal-dual algorithm is in the spirit of the work Buchbinder, Kimbrel, Levi, Makarychev, and Sviridenko, which maintains a wavefront dual solution to decide when to place an order and which items to order. The main twist is in deciding which requests to serve early. In contrast to the work of Moseley et al., which ranks early requests in ascending order of desired service time and serves them until their total holding cost matches the ordering cost incurred for that item, we extend to the non-uniform case by instead ranking in ascending order of when the delay cost of a demand would reach its current holding cost. An important special case of the JRP is the single-item lot-sizing problem. Here, Moseley et al. gave a 3-competitive algorithm when the holding and delay costs are uniform across demands. We provide a new algorithm for which the competitive ratio is $φ+1 \approx 2.681$, where $φ$ is the golden ratio, which again holds for arbitrary monotone holding-delay costs. - 30 October 2025
- Published by Springer Nature in Mathematical Programming
- Vol. 216 (1-2) , 489-520
Network flow problems with electric vehicles
- 30 October 2025
- Published by Springer Nature in Mathematical Programming
- Vol. 216 (1-2) , 489-520
Network flow problems with electric vehicles
- 12 February 2025
- Published by Springer Nature
- p. 167-182
Small Additive Error for Unsplittable Multicommodity Flow in Outerplanar Graphs
- 12 February 2025
- Published by Springer Nature
- p. 167-182
Small Additive Error for Unsplittable Multicommodity Flow in Outerplanar Graphs
- 12 February 2025
- Published by Springer Nature
- p. 1-15
Bounding the Price-of-Fair-Sharing Using Knapsack-Cover Constraints to Guide Near-Optimal Cost-Recovery Algorithms
- 12 February 2025
- Published by Springer Nature
- p. 1-15
Bounding the Price-of-Fair-Sharing Using Knapsack-Cover Constraints to Guide Near-Optimal Cost-Recovery Algorithms
- 1 November 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Applied Analytics
- Vol. 54 (6) , 537-552
Modeling the Risk of In-Person Instruction During the COVID-19 Pandemic
We use mathematical modeling and simulation to evaluate the safety of in-person instruction in university classrooms under different interventions. We find that, for the Delta variant of COVID-19, requiring masking when more than 90% of students are vaccinated is safe and easy to implement, without needing to assign fixed seats or improving the ventilation in classrooms. Our model supported Cornell University to safely conduct in-person instruction in fall 2021.
- 1 November 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Applied Analytics
- Vol. 54 (6) , 537-552
Modeling the Risk of In-Person Instruction During the COVID-19 Pandemic
We use mathematical modeling and simulation to evaluate the safety of in-person instruction in university classrooms under different interventions. We find that, for the Delta variant of COVID-19, requiring masking when more than 90% of students are vaccinated is safe and easy to implement, without needing to assign fixed seats or improving the ventilation in classrooms. Our model supported Cornell University to safely conduct in-person instruction in fall 2021.
- Open Access
Modeling the Risk of In-Person Instruction during the COVID-19 Pandemic
During the COVID-19 pandemic, safely implementing in-person indoor instruction was a high priority for universities nationwide. To support this effort at the University, we developed a mathematical model for estimating the risk of SARS-CoV-2 transmission in university classrooms. This model was used to evaluate combinations of feasible interventions for classrooms at the University during the pandemic and optimize the set of interventions that would allow higher occupancy levels, matching the pre-pandemic numbers of in-person courses. Importantly, we determined that requiring masking in dense classrooms with unrestricted seating with more than 90% of students vaccinated was easy to implement, incurred little logistical or financial cost, and allowed classes to be held at full capacity. A retrospective analysis at the end of the semester confirmed the model's assessment that the proposed classroom configuration would be safe. Our framework is generalizable and was used to support reopening decisions at Stanford University. In addition, our framework is flexible and applies to a wide range of indoor settings. It was repurposed for large university events and gatherings and could be used to support planning indoor space use to avoid transmission of infectious diseases across various industries, from secondary schools to movie theaters and restaurants.
Open AccessModeling the Risk of In-Person Instruction during the COVID-19 Pandemic
During the COVID-19 pandemic, safely implementing in-person indoor instruction was a high priority for universities nationwide. To support this effort at the University, we developed a mathematical model for estimating the risk of SARS-CoV-2 transmission in university classrooms. This model was used to evaluate combinations of feasible interventions for classrooms at the University during the pandemic and optimize the set of interventions that would allow higher occupancy levels, matching the pre-pandemic numbers of in-person courses. Importantly, we determined that requiring masking in dense classrooms with unrestricted seating with more than 90% of students vaccinated was easy to implement, incurred little logistical or financial cost, and allowed classes to be held at full capacity. A retrospective analysis at the end of the semester confirmed the model's assessment that the proposed classroom configuration would be safe. Our framework is generalizable and was used to support reopening decisions at Stanford University. In addition, our framework is flexible and applies to a wide range of indoor settings. It was repurposed for large university events and gatherings and could be used to support planning indoor space use to avoid transmission of infectious diseases across various industries, from secondary schools to movie theaters and restaurants.
- 22 December 2023
- Published by Springer Nature
- p. 160-174
Hitting Sets when the Shallow Cell Complexity is Small
- 22 December 2023
- Published by Springer Nature
- p. 160-174
Hitting Sets when the Shallow Cell Complexity is Small