David B. Shmoys

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

Collaborative distances:
  • Dijkstra number2 of four.
  • 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 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

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. Discrete 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

Minimizing Multimodular Functions and Allocating Capacity in Bike-Sharing Systems.
Proceedings of the Integer Programming and Combinatorial Optimization, 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

Minimizing Multimodular Functions and Allocating Capacity in Bike-Sharing Systems.
CoRR, 2016

A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems.
CoRR, 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

Maximizing the Spread of Cascades Using Network Design
CoRR, 2012

Improving christofides' algorithm for the s-t path TSP.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

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

Improving Christofides' Algorithm for the s-t Path TSP
CoRR, 2011

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

Approximation Algorithms for Fragmenting a Graph against a Stochastically-Located Threat.
Proceedings of the Approximation and Online Algorithms - 9th International Workshop, 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.
Operations Research, 2010

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

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

Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem.
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.
Management Science, 2008

Approximation Algorithms for Capacitated Stochastic Inventory Control Models.
Operations Research, 2008

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

Primal-Dual Schema for Capacitated Covering Problems.
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

Approximation Algorithms for 2-Stage Stochastic Optimization Problems.
Proceedings of the FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 2006

2005
The MSOM Society Student Paper Competition: Extended Abstracts of 2004 Winners.
Manufacturing & Service Operations Management, 2005

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

Approximation Algorithms for Stochastic Inventory Control Models.
Proceedings of the Integer Programming and Combinatorial Optimization, 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.
Annals OR, 2004

Primal-dual algorithms for deterministic inventory problems.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

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

LP-based Approximation Algorithms for Capacitated Facility Location.
Proceedings of the Integer Programming and Combinatorial Optimization, 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

Fault-tolerant facility location.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

An improved approximation algorithm for the partial latin square extension problem.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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 k-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.
Operations Research, 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

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
Improved Approximation Algorithms for Shop Scheduling Problems.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

Scheduling Parallel Machines On-Line
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Fast Approximation Algorithms for Fractional Packing and Covering Problems
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Scheduling Parallel Machines On-line.
Proceedings of the On-Line Algorithms, 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

Approximation Algorithms for Scheduling Unrelated Parallel Machines
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 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 k-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

Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984
Recognizing graphs with fixed interval number is NP-complete.
Discrete Applied Mathematics, 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...