David Shmoys | Academic Influence

David Shmoys's AcademicInfluence.com Rankings

David Shmoys

Mathematics

#2840

World Rank

#4302

Historical Rank

#1097

USA Rank

Operations Research

#20

World Rank

#20

Historical Rank

#14

USA Rank

Measure Theory

#978

World Rank

#1271

Historical Rank

#365

USA Rank

mathematics Degrees

Download Badge

Mathematics

David Shmoys's Degrees

PhD Operations Research Stanford University
Bachelors Mathematics Stanford University

Similar Degrees You Can Earn

Best Online Bachelor's in Math 2025

Why Is David Shmoys Influential?

(Suggest an Edit or Addition)

According to Wikipedia, David Bernard Shmoys is a Professor in the School of Operations Research and Information Engineering and the Department of Computer Science at Cornell University. He obtained his Ph.D. from the University of California, Berkeley in 1984. His major focus has been in the design and analysis of algorithms for discrete optimization problems.

(See a Problem?)

David Shmoys's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Sequencing and scheduling: algorithms and complexity (1989) (1567)
The traveling salesman problem (1985) (1311)
The Design of Approximation Algorithms (2011) (1110)
A Best Possible Heuristic for the k-Center Problem (1985) (968)
Approximation algorithms for scheduling unrelated parallel machines (1987) (960)
Using dual approximation algorithms for scheduling problems: Theoretical and practical results (1985) (730)
An approximation algorithm for the generalized assignment problem (1993) (714)
Fast approximation algorithms for fractional packing and covering problems (1991) (677)
Approximation algorithms for facility location problems (2000) (624)
A Constant-Factor Approximation Algorithm for the k-Median Problem (2002) (585)
Approximation algorithms for facility location problems (extended abstract) (1997) (556)
Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms (1997) (492)
Chapter 9 Sequencing and scheduling: Algorithms and complexity (1993) (476)
Dynamic Assortment Optimization with a Multinomial Logit Choice Model and Capacity Constraint (2010) (391)
Erratum: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (1986) (363)
A unified approach to approximation algorithms for bottleneck problems (1986) (363)
A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach (1988) (334)
Improved Approximation Algorithms for the Uncapacitated Facility Location Problem (2003) (305)
Scheduling parallel machines on-line (1991) (296)
Improved approximation algorithms for network design problems (1994) (245)
A constant-factor approximation algorithm for the k-median problem (extended abstract) (1999) (228)
Assortment Optimization under the Multinomial Logit Model with Random Choice Parameters (2014) (226)
Scheduling to minimize average completion time: off-line and on-line algorithms (1996) (226)
Improved approximation algorithms for shop scheduling problems (1991) (212)
Short Shop Schedules (1997) (210)
In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation (2016) (203)
Well-solved special cases (1985) (197)
Provably Near-Optimal Sampling-Based Policies for Stochastic Inventory Control Models (2007) (193)
A New Approach to Computing Optimal Schedules for the Job-Shop Scheduling Problem (1996) (192)
Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better (1992) (166)
Cut problems and their application to divide-and-conquer (1996) (165)
Analyzing the Held-Karp TSP Bound: A Monotonicity Property with Application (1990) (151)
Improved Scheduling Algorithms for Minsum Criteria (1996) (149)
A Guided Tour of Combinatorial Optimization (1985) (137)
Data Analysis and Optimization for (Citi)Bike Sharing (2015) (136)
Selective mapping: a strategy for optimizing the construction of high-density linkage maps. (2000) (132)
Approximation Algorithms for Stochastic Inventory Control Models (2005) (127)
Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds (1997) (126)
A 3-Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem (1999) (122)
An approximation scheme for stochastic linear programming and its application to stochastic integer programs (2006) (118)
Sampling-based approximation algorithms for multi-stage stochastic optimization (2005) (116)
LP-based approximation algorithms for capacitated facility location (2004) (113)
Approximation schemes for constrained scheduling problems (1989) (113)
A constant approximation algorithm for the one-warehouse multi-retailer problem (2005) (112)
Completing Quasigroups or Latin Squares: A Structured Graph Coloring Problem (2002) (110)
Fault-tolerant facility location (2003) (105)
Stochastic optimization is (almost) as easy as deterministic optimization (2004) (105)
Permutation vs. non-permutation flow shop schedules (1991) (98)
Approximation algorithms for 2-stage stochastic optimization problems (2006) (98)
Maximizing the Spread of Cascades Using Network Design (2010) (97)
Using dual approximation algorithms for scheduling problems: practical and theoretical results (1987) (96)
Improved approximation algorithms for a capacitated facility location problem (1999) (91)
Primal-dual algorithms for deterministic inventory problems (2004) (91)
Primal-dual schema for capacitated covering problems (2008) (86)
Predicting Bike Usage for New York City's Bike Sharing System (2015) (85)
Efficient Parallel Algorithms for Edge Coloring Problems (1987) (84)
Approximation Algorithms for Capacitated Stochastic Inventory Control Models (2008) (78)
Sincronia: near-optimal network design for coflows (2018) (76)
Improving Christofides' Algorithm for the s-t Path TSP (2011) (76)
Scheduling unrelated machines with costs (1993) (74)
Simple constant-time consensus protocols in realistic failure models (1989) (73)
A best possible approximation algorithm for the k--center problem (1985) (67)
Sequencing and Scheduling: Algorithms and Complexity, in Logistics of production and inventory (1993) (65)
Computing near-optimal solutions to combinatorial optimization problems (1994) (64)
Combinatorics in computer science (1996) (60)
Facility location with Service Installation Costs (2004) (57)
Minimizing Multimodular Functions and Allocating Capacity in Bike-Sharing Systems (2016) (57)
Recognizing graphs with fixed interval number is NP-complete (1984) (54)
Lagrangian Relaxation for the k-Median Problem: New Insights and Continuity Properties (2003) (52)
A Better than "Best Possible" Algorithm to Edge Color Multigraphs (1986) (52)
A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems (2011) (50)
A PTAS for capacitated sum-of-ratios optimization (2009) (47)
Assortment Optimization with Mixtures of Logits (2010) (44)
Approximation algorithms for supply chain planning and logistics problems with market choice (2011) (44)
A Polynomial Approximation Scheme for Machine Scheduling on Uniform Processors: Using the Dual Approximation Approach (1986) (40)
The Promise of LP to Boost CSP Techniques for Combinatorial Problems (2002) (40)
Bike Angels: An Analysis of Citi Bike's Incentive Program (2018) (37)
The submodular joint replenishment problem (2015) (33)
Improving christofides' algorithm for the s-t path TSP (2012) (33)
An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem (1985) (32)
Using Interior-Point Methods for Fast Parallel Algorithms for Bipartite Matching and Related Problems (1992) (32)
Computing near-optimal schedules (1995) (29)
The Parallel Complexity of TSP Heuristics (1989) (29)
A Constant Approximation Algorithm for the a prioriTraveling Salesman Problem (2008) (29)
Improved Lower Bounds for the Universal and a priori TSP (2010) (28)
Algorithms for the universal and a priori TSP (2008) (27)
Well-solved Special Cases of the Traveling Salesman Problem (1984) (27)
Mathematical Programming Guides Air-Ambulance Routing at Ornge (2013) (27)
An improved approximation algorithm for the partial latin square extension problem (2003) (25)
Addendum: COVID-19 Mathematical Modeling for Cornell’s Fall Semester (2020) (23)
Approximation algorithms for clustering problems (1999) (23)
A time-oriented approach to computing optimal schedules for the job-shop scheduling problem (1996) (22)
Bike Sharing (2019) (21)
Flipping persuasively in constant expected time (1986) (20)
Approximation Algorithms for 2-Stage Stochastic Scheduling Problems (2007) (20)
Modeling for COVID-19 college reopening decisions: Cornell, a case study (2021) (20)
A computational study of the job-shop and the flow-shop scheduling problems (1993) (20)
Interior-point methods in parallel computation (1989) (20)
Approximations and Randomization to Boost CSP Techniques (2004) (19)
The Sample Average Approximation Method for 2-stage Stochastic Optimization (2005) (18)
Provably near-optimal sampling-based algorithms for Stochastic inventory control models (2006) (18)
Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem (1998) (18)
Simple constant-time consensus protocols in realistic failure models (extended abstract) (1985) (18)
Near-Optimal Sequencing with Precedence Constraints (1990) (17)
A constant-factor approximation for the k-median problem (1999) (16)
Flipping Persuasively in Constant Time (1990) (16)
Approximation algorithms for the multi-level facility location problem (2001) (16)
Improved approximation algorithms for minsum criteria (1996) (16)
Powers of graphs: A powerful approximation technique for bottleneck problems (1984) (15)
Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems (2020) (15)
Using Linear Programming in the Design and Analysis of Approximation Algorithms: Two Illustrative Problems (1998) (15)
Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem (2010) (15)
Analytics and Bikes: Riding Tandem with Motivate to Improve Mobility (2019) (15)
Fairmandering: A column generation heuristic for fairness-optimized political districting (2021) (14)
Proceedings of the forty-sixth annual ACM symposium on Theory of computing (2014) (14)
A Bicriteria Approximation Algorithm for the k-Center and k-Median Problems (2017) (14)
Primal-Dual Schema and Lagrangian Relaxation for the k-Location-Routing Problem (2011) (14)
A packing problem you can almost solve by sitting on your suitcase (1986) (12)
Inventory and Facility Location Models with Market Selection (2005) (11)
An improved approximation algorithm for the generalized assignment problem (1993) (11)
Prize-Collecting TSP with a Budget Constraint (2017) (11)
Stochastic optimization is (almost) as easy as discrete optimization (2004) (10)
Data-Driven Rebalancing Methods for Bike-Share Systems (2020) (10)
Scheduling unrelated parallel machines with costs (1992) (9)
Approximation Algorithms for Stochastic Inventory Control Models ( DRAFT ) (2005) (7)
Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines That Run at Fifferent Speeds (Extended Abstract) (1997) (7)
Computing provably near-optimal policies for stochastic inventory control models (2005) (7)
New Policies for Stochastic Inventory Control Models: Theoretical and Computational Results (2007) (7)
LP-Based Approximation Algorithms for Traveling Salesman Path Problems (2011) (6)
Approximation Algorithms for 2-stage and Multi-stage Stochastic Optimization (2005) (5)
Approximation Algorithms for Fragmenting a Graph Against a Stochastically-Located Threat (2011) (4)
Best possible heuristics for the bottleneck wandering salesperson and bottleneck vehicle routing problem (1986) (4)
Elements of Scheduling (2020) (4)
Combatting Gerrymandering with Social Choice: The Design of Multi-member Districts (2021) (3)
Aggregating courier deliveries (2018) (3)
Use of a Novel Application to Optimize Aircraft Utilization for Non-Urgent Patient Transfers (2011) (3)
Improved approximation algorithms for the k-level facility location problem (1999) (3)
Approximation Algorithms for Constrained Scheduling (1992) (3)
An improvement performance guarantee for the partial latin square problem (2002) (2)
On the Power of Static Assignment Policies for Robust Facility Location Problems (2020) (2)
The MSOM Society Student Paper Competition: Extended Abstracts of 2004 Winners (2005) (2)
Some Recent Developments in the Design and Analysis of Approximation Algorithms (1993) (2)
From Switch Scheduling to Datacenter Scheduling: Matching-Coordinated Greed is Good (2022) (2)
Weighted sum of completion times (2006) (2)
Optimal Network Design for the Spread of Cascades (2010) (2)
Scheduling Appointments Online: The Power of Deferred Decision-Making (2021) (1)
Sincronia (2018) (1)
A novel application to optimize utilization for nonurgent air transfers. (2014) (1)
Scheduling to minimize av-emge completion time (1997) (1)
Boosters protect against SARS-CoV-2 infections in young adults during an Omicron-predominant period (2022) (1)
Approximation algorithms via the primal-dual schema: applications of the simple dual-ascent method to problems from logistics (2010) (1)
Primal-dual schema for capacitated covering problems (2014) (1)
An Introduction to the Techniques (1)
Preface (Special issue in memory of Eugene L. Lawler (1933-1994)) (1998) (1)
GILP: An Interactive Tool for Visualizing the Simplex Algorithm (2022) (1)
Approximation Algorithms (1997) (1)
The Design of Approximation Algorithms: Rounding Data and Dynamic Programming (2011) (1)
The Design of Approximation Algorithms: Further Uses of Random Sampling and Randomized Rounding of Linear Programs (2011) (1)
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, January 9-11, 2000, San Francisco, CA, USA (2000) (1)
Book review: The Travelling Salesman Problem: A Computational Study (2009) (1)
Approximation algorithms for stochastic combinatorial optimization, with applications in sustainability (2012) (1)
The Design of Approximation Algorithms: Random Sampling and Randomized Rounding of Linear Programs (2011) (0)
Chapter 40 Combinatorics in Computer Science (1990) (0)
Booster vaccination protection against SARS-CoV-2 infections in young adults during an Omicron BA.1-predominant period: A retrospective cohort study (2023) (0)
Parallel machines - Minmax criteria, no preemption (2019) (0)
Crowdsourcing Operations: Incentivizing Bike Angels in America (2019) (0)
LP-based approximation algorithms for capacitated facility location (2010) (0)
SPT optimality (mostly) via linear programming (2022) (0)
Minmax criteria, no preemption (2019) (0)
The Design of Approximation Algorithms: Cuts and Metrics (2011) (0)
Scheduling (Dagstuhl Seminar 20081) (2020) (0)
Session details: 1B (2008) (0)
Foreword (2004) (0)
A Final Assignment: (2019) (0)
The Design of Approximation Algorithms: Bibliography (2011) (0)
The Design of Approximation Algorithms: Further Uses of the Primal-Dual Method (2011) (0)
5 CUT PROBLEMSAND THEIR APPLICATION TO DIVIDE-AND-CONQUER (1996) (0)
The Design of Approximation Algorithms: An Introduction to Approximation Algorithms (2011) (0)
Scheduling with Predictions (2022) (0)
The single machine - Minmax criteria (2019) (0)
Multi-operation models - Flow shops (2019) (0)
The Design of Approximation Algorithms: Further Uses of Cuts and Metrics (2011) (0)
The Design of Approximation Algorithms: Linear Programming (2011) (0)
The Design of Approximation Algorithms: Greedy Algorithms and Local Search (2011) (0)
The Design of Approximation Algorithms: Further Uses of Rounding Data and Dynamic Programming (2011) (0)
The Design of Approximation Algorithms: Preface (2011) (0)
Flow Shops (2019) (0)
Minmax criteria (2019) (0)
An Interpretable Determinantal Choice Model for Subset Selection (2023) (0)
The Design of Approximation Algorithms: The Primal-Dual Method (2011) (0)
Strategic directions in research in theory of computing (1997) (0)
Hitting Sets when the Shallow Cell Complexity is Small (2023) (0)
Selected papers of Eugene L. Lawler (1999) (0)
Preliminaries - Deterministic Machine Scheduling Problems (2019) (0)
Session details: 6 (2008) (0)
In Memoriam: Eugene L. Lawler (1994) (0)
A randomized variation on a theorem of Lenstra (2011) (0)
MIT Open Access Articles The submodular joint replenishment problem (2022) (0)
The Design and Analysis of Approximation Algorithms: Facility Location as a Case Study (2021) (0)
David Shmoys (2019) (0)
The Design of Approximation Algorithms: Deterministic Rounding of Linear Programs (2011) (0)
The Soviet Ellipsoid Method and Its Application to Combinatorial Optimization Problems (2017) (0)
Book review: The traveling salesman problem: a computational study (by D.L. Applegate, R.E. Bixby, V. Chvátal, W.J. Cook) (2009) (0)
Approximation Algorithms for Fragmenting a Graph Against a Stochastically-Located Threat (2014) (0)
Selected publications of Eugene L. Lawler (1999) (0)
VLSI Design, Parallel Computation and Distributed Computing (1991) (0)
The Design of Approximation Algorithms: Further Uses of Randomized Rounding of Semidefinite Programs (2011) (0)
The Design of Approximation Algorithms: Techniques in Proving the Hardness of Approximation (2011) (0)
The submodular joint replenishment problem (2015) (0)
A min-max theorem for the minimum fleet-size problem (2022) (0)
The Design of Approximation Algorithms: NP-Completeness (2011) (0)
Combinatorial Approximation Algorithms (Dagstuhl Seminar 9734) (2021) (0)
Approximation algorithms for problems in sequencing, scheduling, and communication network design (complexity, coloring, np-complete) (1984) (0)
A Simpler Primal-Dual Proof of Lawler ’ s Algorithm (2009) (0)
Computational complexity (1996) (0)
R 5 CUT PROBLEMS AND THEIR APPLICATION TO DIVIDE-AND-CONQUER (2021) (0)
The Design of Approximation Algorithms: Randomized Rounding of Semidefinite Programs (2011) (0)
The Design of Approximation Algorithms: Open Problems (2011) (0)
PUpping Persuasively in CODstant Expeeted Time (Preliminary version) (1986) (0)
Erratum to “Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems” (2022) (0)
The Design of Approximation Algorithms: Further Uses of Greedy and Local Search Algorithms (2011) (0)
Approximation Algorithms (cid:3) (2021) (0)
The Design of Approximation Algorithms: Further Uses of Deterministic Rounding of Linear Programs (2011) (0)
Flipping Persuasively in Constant Expected Time (Preliminary Version) (1986) (0)

This paper list is powered by the following services:

Other Resources About David Shmoys

en.wikipedia.org

What Schools Are Affiliated With David Shmoys?

David Shmoys is affiliated with the following schools:

Image Attributions

Image Source for David Shmoys