David B. Shmoys
According to our database^{1},
David B. Shmoys
authored at least 98 papers
between 1984 and 2018.
Collaborative distances:
Collaborative distances:
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 OtherLinks
Homepages:

at id.loc.gov

at dnb.info
On csauthors.net:
Bibliography
2018
Sincronia: nearoptimal 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 PrimalDual Approximation Algorithm for MinSum SingleMachine Scheduling Problems.
SIAM J. Discrete Math., 2017
A Bicriteria Approximation Algorithm for the kCenter and kMedian Problems.
Proceedings of the Approximation and Online Algorithms  15th International Workshop, 2017
Minimizing Multimodular Functions and Allocating Capacity in BikeSharing Systems.
Proceedings of the Integer Programming and Combinatorial Optimization, 2017
PrizeCollecting 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
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 TwentyNinth AAAI Conference on Artificial Intelligence, 2015
2013
Mathematical Programming Guides AirAmbulance Routing at Ornge.
Interfaces, 2013
2012
SamplingBased Approximation Algorithms for Multistage Stochastic Optimization.
SIAM J. Comput., 2012
Improving christofides' algorithm for the st 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
Approximation Algorithms for Fragmenting a Graph against a StochasticallyLocated Threat.
Proceedings of the Approximation and Online Algorithms  9th International Workshop, 2011
A PrimalDual Approximation Algorithm for MinSum SingleMachine Scheduling Problems.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011
PrimalDual Schema and Lagrangian Relaxation for the kLocationRouting Problem.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011
The Design of Approximation Algorithms.
Cambridge University Press, ISBN: 9780521195270, 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 sumofratios optimization.
Oper. Res. Lett., 2009
2008
Algorithms for the universal and a priori TSP.
Oper. Res. Lett., 2008
A Constant Approximation Algorithm for the OneWarehouse 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
PrimalDual Schema for Capacitated Covering Problems.
Proceedings of the Integer Programming and Combinatorial Optimization, 2008
2007
Provably NearOptimal SamplingBased Policies for Stochastic Inventory Control Models.
Math. Oper. Res., 2007
Approximation Algorithms for 2Stage Stochastic Scheduling Problems.
Proceedings of the Integer Programming and Combinatorial Optimization, 2007
Samplingbased Approximation Algorithms for Multistage Stochastic Optimization.
Proceedings of the Probabilistic Methods in the Design and Analysis of Algorithms, 23.09., 2007
2006
An approximation scheme for stochastic linear programming and its application to stochastic integer programs.
J. ACM, 2006
Provably nearoptimal samplingbased algorithms for Stochastic inventory control models.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006
Approximation Algorithms for 2Stage 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 onewarehouse multiretailer problem.
Proceedings of the Sixteenth Annual ACMSIAM 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
Samplingbased Approximation Algorithms for Multistage Stochastic.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005
Approximation Algorithms for 2stage and Multistage Stochastic Optimization.
Proceedings of the Algorithms for Optimization with Incomplete Information, 2005
2004
Foreword.
J. Algorithms, 2004
Approximations and Randomization to Boost CSP Techniques.
Annals OR, 2004
Primaldual 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 ACMSIAM Symposium on Discrete Algorithms, 2004
LPbased 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
Faulttolerant facility location.
Proceedings of the Fourteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2003
An improved approximation algorithm for the partial latin square extension problem.
Proceedings of the Fourteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2003
Lagrangian Relaxation for the kMedian Problem: New Insights and Continuity Properties.
Proceedings of the Algorithms, 2003
2002
A ConstantFactor Approximation Algorithm for the kMedian 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 PrecedenceConstrained Scheduling Problems on Parallel Machines that Run at Different Speeds.
J. Algorithms, 1999
A 3Approximation Algorithm for the kLevel Uncapacitated Facility Location Problem.
Inf. Process. Lett., 1999
A ConstantFactor Approximation Algorithm for the kMedian Problem (Extended Abstract).
Proceedings of the ThirtyFirst Annual ACM Symposium on Theory of Computing, 1999
Improved Approximation Algorithms for a Capacitated Facility Location Problem.
Proceedings of the Tenth Annual ACMSIAM 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: OffLine and OnLine Approximation Algorithms.
Math. Oper. Res., 1997
Short Shop Schedules.
Operations Research, 1997
Approximation Algorithms for Facility Location Problems (Extended Abstract).
Proceedings of the TwentyNinth Annual ACM Symposium on the Theory of Computing, 1997
Approximation Algorithms for PrecedenceConstrained Scheduling Problems on Parallel Machines That Run at Fifferent Speeds (Extended Abstract).
Proceedings of the Eighth Annual ACMSIAM Symposium on Discrete Algorithms, 1997
1996
Scheduling to Minimize Average Completion Time: Offline and Online Algorithms.
Proceedings of the Seventh Annual ACMSIAM Symposium on Discrete Algorithms, 1996
A New Approach to Computing Optimal Schedules for the JobShop 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
Fast Approximation Algorithms for Fractional Packing and Covering Problems.
Math. Oper. Res., 1995
1994
Improved Approximation Algorithms for Network Design Problems.
Proceedings of the Fifth Annual ACMSIAM Symposium on Discrete Algorithms. 2325 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/SIGACTSIAM Symposium on Discrete Algorithms, 1993
Computing nearoptimal solutions to combinatorial optimization problems.
Proceedings of the Combinatorial Optimization, 1993
1992
Using InteriorPoint Methods for Fast Parallel Algorithms for Bipartite Matching and Related Problems.
SIAM J. Comput., 1992
Jackson's Rule for SingleMachine Scheduling: Making a Good Heuristic Better.
Math. Oper. Res., 1992
1991
Improved Approximation Algorithms for Shop Scheduling Problems.
Proceedings of the Second Annual ACM/SIGACTSIAM Symposium on Discrete Algorithms, 1991
Scheduling Parallel Machines OnLine
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 Online.
Proceedings of the OnLine Algorithms, 1991
1990
Flipping Persuasively in Constant Time.
SIAM J. Comput., 1990
Approximation Algorithms for Scheduling Unrelated Parallel Machines.
Math. Program., 1990
Analyzing the HeldKarp TSP Bound: A Monotonicity Property with Application.
Inf. Process. Lett., 1990
NearOptimal 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 constanttime 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
InteriorPoint 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 kCenter Problem.
Math. Oper. Res., 1985
Simple ConstantTime 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 NPcomplete.
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