David B. Shmoys

Orcid: 0000-0003-3882-901X

Affiliations:
  • Cornell University, Ithaca, USA


According to our database1, David B. Shmoys authored at least 119 papers between 1984 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2001, "For fundamental achievements in the design and analysis of algorithms for discrete optimization problems.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Improved Approximation Algorithms for the Joint Replenishment Problem with Outliers, and with Fairness Constraints.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Harmony: A Congestion-free Datacenter Architecture.
Proceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation, 2024

Network Flow Problems with Electric Vehicles.
Proceedings of the Integer Programming and Combinatorial Optimization, 2024

2023
A min-max theorem for the minimum fleet-size problem.
Oper. Res. Lett., May, 2023

Scheduling (Dagstuhl Seminar 23061).
Dagstuhl Reports, February, 2023

SPT optimality (mostly) via linear programming.
Oper. Res. Lett., January, 2023

Sharing the Cost of IoT Wireless Coverage with a Strengthened Linear Programming Formulation.
CoRR, 2023

An Interpretable Determinantal Choice Model for Subset Selection.
CoRR, 2023

Hitting Sets when the Shallow Cell Complexity is Small.
Proceedings of the Approximation and Online Algorithms - 21st International Workshop, 2023

GILP: An Interactive Tool for Visualizing the Simplex Algorithm.
Proceedings of the 54th ACM Technical Symposium on Computer Science Education, Volume 1, 2023

2022
Minimizing Multimodular Functions and Allocating Capacity in Bike-Sharing Systems.
Oper. Res., 2022

Scheduling with Predictions.
CoRR, 2022

GILP: An Interactive Tool for Visualizing the Simplex Algorithm.
CoRR, 2022

Scheduling Appointments Online: The Power of Deferred Decision-Making.
Proceedings of the Approximation and Online Algorithms - 20th International Workshop, 2022

Combatting Gerrymandering with Social Choice: The Design of Multi-member Districts.
Proceedings of the EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11, 2022

From Switch Scheduling to Datacenter Scheduling: Matching-Coordinated Greed is Good.
Proceedings of the PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25, 2022

2021
Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem.
ACM Trans. Algorithms, 2021

On the Power of Static Assignment Policies for Robust Facility Location Problems.
Proceedings of the Integer Programming and Combinatorial Optimization, 2021

Fairmandering: A column generation heuristic for fairness-optimized political districting.
Proceedings of the 2021 SIAM Conference on Applied and Computational Discrete Algorithms, 2021

2020
Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems.
Math. Oper. Res., 2020

Scheduling (Dagstuhl Seminar 20081).
Dagstuhl Reports, 2020

Elements of Scheduling.
CoRR, 2020

2019
Analytics and Bikes: Riding Tandem with Motivate to Improve Mobility.
INFORMS J. Appl. Anal., 2019

Computational sustainability: computing for a better world and a sustainable future.
Commun. ACM, 2019

2018
Sincronia: near-optimal network design for coflows.
Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication, 2018

Bike Angels: An Analysis of Citi Bike's Incentive Program.
Proceedings of the 1st ACM SIGCAS Conference on Computing and Sustainable Societies, 2018

2017
A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems.
SIAM J. Discret. Math., 2017

A Bicriteria Approximation Algorithm for the k-Center and k-Median Problems.
Proceedings of the Approximation and Online Algorithms - 15th International Workshop, 2017

Prize-Collecting TSP with a Budget Constraint.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016
The submodular joint replenishment problem.
Math. Program., 2016

2015
Approximation Algorithms for Fragmenting a Graph Against a Stochastically-Located Threat.
Theory Comput. Syst., 2015

Primal-dual schema for capacitated covering problems.
Math. Program., 2015

Improving Christofides' Algorithm for the s-t Path TSP.
J. ACM, 2015

Predicting Bike Usage for New York City's Bike Sharing System.
Proceedings of the Computational Sustainability, 2015

Data Analysis and Optimization for (Citi)Bike Sharing.
Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015

2013
Mathematical Programming Guides Air-Ambulance Routing at Ornge.
Interfaces, 2013

2012
Sampling-Based Approximation Algorithms for Multistage Stochastic Optimization.
SIAM J. Comput., 2012

LP-based approximation algorithms for capacitated facility location.
Math. Program., 2012

2011
Approximation algorithms for supply chain planning and logistics problems with market choice.
Math. Program., 2011

LP-Based Approximation Algorithms for Traveling Salesman Path Problems
CoRR, 2011

A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

Primal-Dual Schema and Lagrangian Relaxation for the k-Location-Routing Problem.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

The Design of Approximation Algorithms.
Cambridge University Press, ISBN: 978-0-521-19527-0, 2011

2010
Dynamic Assortment Optimization with a Multinomial Logit Choice Model and Capacity Constraint.
Oper. Res., 2010

Maximizing the Spread of Cascades Using Network Design.
Proceedings of the UAI 2010, 2010

Improved Lower Bounds for the Universal and <i>a priori</i> TSP.
Proceedings of the Approximation, 2010

2009
A PTAS for capacitated sum-of-ratios optimization.
Oper. Res. Lett., 2009

2008
Fault-tolerant facility location.
ACM Trans. Algorithms, 2008

Algorithms for the universal and a priori TSP.
Oper. Res. Lett., 2008

A Constant Approximation Algorithm for the One-Warehouse Multiretailer Problem.
Manag. Sci., 2008

Approximation Algorithms for Capacitated Stochastic Inventory Control Models.
Oper. Res., 2008

A Constant Approximation Algorithm for the a prioriTraveling Salesman Problem.
Proceedings of the Integer Programming and Combinatorial Optimization, 2008

2007
Provably Near-Optimal Sampling-Based Policies for Stochastic Inventory Control Models.
Math. Oper. Res., 2007

Approximation Algorithms for Stochastic Inventory Control Models.
Math. Oper. Res., 2007

Approximation Algorithms for 2-Stage Stochastic Scheduling Problems.
Proceedings of the Integer Programming and Combinatorial Optimization, 2007

Sampling-based Approximation Algorithms for Multi-stage Stochastic Optimization.
Proceedings of the Probabilistic Methods in the Design and Analysis of Algorithms, 23.09., 2007

2006
Approximation algorithms for 2-stage stochastic optimization problems.
SIGACT News, 2006

Primal-Dual Algorithms for Deterministic Inventory Problems.
Math. Oper. Res., 2006

An approximation scheme for stochastic linear programming and its application to stochastic integer programs.
J. ACM, 2006

Provably near-optimal sampling-based algorithms for Stochastic inventory control models.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

2005
The MSOM Society Student Paper Competition: Extended Abstracts of 2004 Winners.
Manuf. Serv. Oper. Manag., 2005

A constant approximation algorithm for the one-warehouse multi-retailer problem.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Inventory and Facility Location Models with Market Selection.
Proceedings of the Integer Programming and Combinatorial Optimization, 2005

Sampling-based Approximation Algorithms for Multi-stage Stochastic.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Approximation Algorithms for 2-stage and Multi-stage Stochastic Optimization.
Proceedings of the Algorithms for Optimization with Incomplete Information, 2005

2004
An improved approximation algorithm for the partial Latin square extension problem.
Oper. Res. Lett., 2004

Foreword.
J. Algorithms, 2004

Approximations and Randomization to Boost CSP Techniques.
Ann. Oper. Res., 2004

Facility location with Service Installation Costs.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Stochastic Optimization is (Almost) as easy as Deterministic Optimization.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003
Improved Approximation Algorithms for the Uncapacitated Facility Location Problem.
SIAM J. Comput., 2003

Lagrangian Relaxation for the k-Median Problem: New Insights and Continuity Properties.
Proceedings of the Algorithms, 2003

2002
A Constant-Factor Approximation Algorithm for the k-Median Problem.
J. Comput. Syst. Sci., 2002

2000
Approximation algorithms for facility location problems.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999
Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds.
J. Algorithms, 1999

A 3-Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem.
Inf. Process. Lett., 1999

A Constant-Factor Approximation Algorithm for the <i>k</i>-Median Problem (Extended Abstract).
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Improved Approximation Algorithms for a Capacitated Facility Location Problem.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Approximation Algorithms for Clustering Problems.
Proceedings of the Twelfth Annual Conference on Computational Learning Theory, 1999

1998
Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem.
J. Comb. Optim., 1998

Using Linear Programming in the Design and Analysis of Approximation Algorithms: Two Illustrative Problems.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 1998

1997
Strategic directions in research in theory of computing.
SIGACT News, 1997

Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms.
Math. Oper. Res., 1997

Short Shop Schedules.
Oper. Res., 1997

Approximation Algorithms for Facility Location Problems (Extended Abstract).
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines That Run at Fifferent Speeds (Extended Abstract).
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

1996
Scheduling to Minimize Average Completion Time: Off-line and On-line Algorithms.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

A New Approach to Computing Optimal Schedules for the Job-Shop Scheduling Problem.
Proceedings of the Integer Programming and Combinatorial Optimization, 1996

Improved Scheduling Algorithms for Minsum Criteria.
Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

1995
Scheduling Parallel Machines On-Line.
SIAM J. Comput., 1995

Fast Approximation Algorithms for Fractional Packing and Covering Problems.
Math. Oper. Res., 1995

1994
Improved Approximation Algorithms for Shop Scheduling Problems.
SIAM J. Comput., 1994

Improved Approximation Algorithms for Network Design Problems.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993
An approximation algorithm for the generalized assignment problem.
Math. Program., 1993

Scheduling Unrelated Machines with Costs.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

Computing near-optimal solutions to combinatorial optimization problems.
Proceedings of the Combinatorial Optimization, 1993

Chapter 9 Sequencing and scheduling: Algorithms and complexity.
Proceedings of the Logistics of Production and Inventory, 1993

1992
Using Interior-Point Methods for Fast Parallel Algorithms for Bipartite Matching and Related Problems.
SIAM J. Comput., 1992

Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better.
Math. Oper. Res., 1992

1991
Permutation vs. non-permutation flow shop schedules.
Oper. Res. Lett., 1991

1990
Flipping Persuasively in Constant Time.
SIAM J. Comput., 1990

Approximation Algorithms for Scheduling Unrelated Parallel Machines.
Math. Program., 1990

Analyzing the Held-Karp TSP Bound: A Monotonicity Property with Application.
Inf. Process. Lett., 1990

Near-Optimal Sequencing with Precedence Constraints.
Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, 1990

1989
The Parallel Complexity of TSP Heuristics.
J. Algorithms, 1989

Simple constant-time consensus protocols in realistic failure models.
J. ACM, 1989

Approximation Schemes for Constrained Scheduling Problems
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Interior-Point Methods in Parallel Computation
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988
A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach.
SIAM J. Comput., 1988

1987
Efficient Parallel Algorithms for Edge Coloring Problems.
J. Algorithms, 1987

Using dual approximation algorithms for scheduling problems theoretical and practical results.
J. ACM, 1987

1986
A Better than "Best Possible" Algorithm to Edge Color Multigraphs.
J. Algorithms, 1986

A unified approach to approximation algorithms for bottleneck problems.
J. ACM, 1986

A Polynomial Approximation Scheme for Machine Scheduling on Uniform Processors: Using the Dual Approximation Approach.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1986

Flipping Persuasively in Constant Expected Time (Preliminary Version)
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985
A Best Possible Heuristic for the <i>k</i>-Center Problem.
Math. Oper. Res., 1985

Simple Constant-Time Consensus Protocols in Realistic Failure Models (Extended Abstract).
Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, 1985

1984
Recognizing graphs with fixed interval number is NP-complete.
Discret. Appl. Math., 1984

Powers of Graphs: A Powerful Approximation Technique for Bottleneck Problems
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984


  Loading...