David B. Shmoys

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

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Improved Approximation Algorithms for the Joint Replenishment Problem with Outliers, and with Fairness Constraints.

Varun Suriyanarayana, Varun Sivashankar, Siddharth Gollapudi, David B. Shmoys

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Harmony: A Congestion-free Datacenter Architecture.

Saksham Agarwal, Qizhe Cai, Rachit Agarwal, David B. Shmoys, Amin Vahdat

Proceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation, 2024

2023

A min-max theorem for the minimum fleet-size problem.

Tinghan Ye, David B. Shmoys

Oper. Res. Lett., May, 2023

Scheduling (Dagstuhl Seminar 23061).

Nicole Megow, Benjamin Moseley, David B. Shmoys, Ola Svensson, Sergei Vassilvitskii, Jens Schlöter

Dagstuhl Reports, February, 2023

SPT optimality (mostly) via linear programming.

Woo-Hyung Cho, David B. Shmoys, Shane G. Henderson

Oper. Res. Lett., January, 2023

Network Flow Problems with Electric Vehicles.

Haripriya Pulyassary, Kostas Kollias, Aaron Schild, David B. Shmoys, Manxi Wu

CoRR, 2023

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

Sander Aarts, Manxi Wu, David B. Shmoys

CoRR, 2023

An Interpretable Determinantal Choice Model for Subset Selection.

Sander Aarts, David B. Shmoys, Alex Coy

CoRR, 2023

Hitting Sets when the Shallow Cell Complexity is Small.

Sander Aarts, David B. Shmoys

Proceedings of the Approximation and Online Algorithms - 21st International Workshop, 2023

GILP: An Interactive Tool for Visualizing the Simplex Algorithm.

Henry W. Robbins, Samuel C. Gutekunst, David B. Shmoys, David P. Williamson

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.

Daniel Freund, Shane G. Henderson, David B. Shmoys

Oper. Res., 2022

Scheduling with Predictions.

Woo-Hyung Cho, Shane G. Henderson, David B. Shmoys

CoRR, 2022

GILP: An Interactive Tool for Visualizing the Simplex Algorithm.

Henry W. Robbins, Samuel C. Gutekunst, Frans Schalekamp, David B. Shmoys, David P. Williamson

CoRR, 2022

Scheduling Appointments Online: The Power of Deferred Decision-Making.

Devin Smedira, David B. Shmoys

Proceedings of the Approximation and Online Algorithms - 20th International Workshop, 2022

Combatting Gerrymandering with Social Choice: The Design of Multi-member Districts.

Nikhil Garg, Wes Gurnee, David Rothschild, David B. Shmoys

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.

Rachit Agarwal, Shijin Rajakrishnan, David B. Shmoys

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.

Hyung-Chan An, Robert Kleinberg, David B. Shmoys

ACM Trans. Algorithms, 2021

On the Power of Static Assignment Policies for Robust Facility Location Problems.

Omar El Housni, Vineet Goyal, David B. Shmoys

Proceedings of the Integer Programming and Combinatorial Optimization, 2021

Fairmandering: A column generation heuristic for fairness-optimized political districting.

Wes Gurnee, David B. Shmoys

Proceedings of the 2021 SIAM Conference on Applied and Computational Discrete Algorithms, 2021

2020

Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems.

Alice Paul, Daniel Freund, Aaron M. Ferber, David B. Shmoys, David P. Williamson

Math. Oper. Res., 2020

Scheduling (Dagstuhl Seminar 20081).

Nicole Megow, David B. Shmoys, Ola Svensson

Dagstuhl Reports, 2020

Elements of Scheduling.

Jan Karel Lenstra, David B. Shmoys

CoRR, 2020

2019

Analytics and Bikes: Riding Tandem with Motivate to Improve Mobility.

Daniel Freund, Shane G. Henderson, Eoin O'Mahony, David B. Shmoys

INFORMS J. Appl. Anal., 2019

Computational sustainability: computing for a better world and a sustainable future.

Carla P. Gomes, Thomas G. Dietterich, Christopher Barrett, Jon Conrad, Bistra Dilkina, Stefano Ermon, Fei Fang, Andrew Farnsworth, Alan Fern, Xiaoli Z. Fern, Daniel Fink, Douglas H. Fisher, Alexander Flecker, Daniel Freund, Angela Fuller, John M. Gregoire, John E. Hopcroft, Steve Kelling, J. Zico Kolter, Warren B. Powell, Nicole D. Sintov, John S. Selker, Bart Selman, Daniel Sheldon, David B. Shmoys, Milind Tambe, Weng-Keen Wong, Christopher Wood, Xiaojian Wu, Yexiang Xue, Amulya Yadav, Abdul-Aziz Yakubu, Mary Lou Zeeman

Commun. ACM, 2019

2018

Sincronia: near-optimal network design for coflows.

Saksham Agarwal, Shijin Rajakrishnan, Akshay Narayan, Rachit Agarwal, David B. Shmoys, Amin Vahdat

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.

Hangil Chung, Daniel Freund, David B. Shmoys

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.

Maurice Cheung, Julián Mestre, David B. Shmoys, José Verschae

SIAM J. Discret. Math., 2017

A Bicriteria Approximation Algorithm for the k-Center and k-Median Problems.

Soroush Alamdari, David B. Shmoys

Proceedings of the Approximation and Online Algorithms - 15th International Workshop, 2017

Prize-Collecting TSP with a Budget Constraint.

Alice Paul, Daniel Freund, Aaron M. Ferber, David B. Shmoys, David P. Williamson

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016

The submodular joint replenishment problem.

Maurice Cheung, Adam N. Elmachtoub, Retsef Levi, David B. Shmoys

Math. Program., 2016

2015

Approximation Algorithms for Fragmenting a Graph Against a Stochastically-Located Threat.

David B. Shmoys, Gwen Spencer

Theory Comput. Syst., 2015

Primal-dual schema for capacitated covering problems.

Tim Carnes, David B. Shmoys

Math. Program., 2015

Improving Christofides' Algorithm for the s-t Path TSP.

Hyung-Chan An, Robert D. Kleinberg, David B. Shmoys

J. ACM, 2015

Predicting Bike Usage for New York City's Bike Sharing System.

Divya Singhvi, Somya Singhvi, Peter I. Frazier, Shane G. Henderson, Eoin O'Mahony, David B. Shmoys, Dawn B. Woodard

Proceedings of the Computational Sustainability, 2015

Data Analysis and Optimization for (Citi)Bike Sharing.

Eoin O'Mahony, David B. Shmoys

Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015

2013

Mathematical Programming Guides Air-Ambulance Routing at Ornge.

Timothy A. Carnes, Shane G. Henderson, David B. Shmoys, Mahvareh Ahghari, Russell D. MacDonald

Interfaces, 2013

2012

Sampling-Based Approximation Algorithms for Multistage Stochastic Optimization.

Chaitanya Swamy, David B. Shmoys

SIAM J. Comput., 2012

LP-based approximation algorithms for capacitated facility location.

Retsef Levi, David B. Shmoys, Chaitanya Swamy

Math. Program., 2012

2011

Approximation algorithms for supply chain planning and logistics problems with market choice.

Joseph Geunes, Retsef Levi, H. Edwin Romeijn, David B. Shmoys

Math. Program., 2011

LP-Based Approximation Algorithms for Traveling Salesman Path Problems

Hyung-Chan An, David B. Shmoys

CoRR, 2011

A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems.

Maurice Cheung, David B. Shmoys

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

Primal-Dual Schema and Lagrangian Relaxation for the k-Location-Routing Problem.

Tim Carnes, David B. Shmoys

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

The Design of Approximation Algorithms.

David P. Williamson, David B. Shmoys

Cambridge University Press, ISBN: 978-0-521-19527-0, 2011

2010

Dynamic Assortment Optimization with a Multinomial Logit Choice Model and Capacity Constraint.

Paat Rusmevichientong, Zuo-Jun Max Shen, David B. Shmoys

Oper. Res., 2010

Maximizing the Spread of Cascades Using Network Design.

Daniel Sheldon, Bistra Dilkina, Adam N. Elmachtoub, Ryan Finseth, Ashish Sabharwal, Jon Conrad, Carla P. Gomes, David B. Shmoys, William Allen, Ole Amundsen, William Vaughan

Proceedings of the UAI 2010, 2010

Improved Lower Bounds for the Universal and <i>a priori</i> TSP.

Igor Gorodezky, Robert D. Kleinberg, David B. Shmoys, Gwen Spencer

Proceedings of the Approximation, 2010

2009

A PTAS for capacitated sum-of-ratios optimization.

Paat Rusmevichientong, Zuo-Jun Max Shen, David B. Shmoys

Oper. Res. Lett., 2009

2008

Fault-tolerant facility location.

Chaitanya Swamy, David B. Shmoys

ACM Trans. Algorithms, 2008

Algorithms for the universal and a priori TSP.

Frans Schalekamp, David B. Shmoys

Oper. Res. Lett., 2008

A Constant Approximation Algorithm for the One-Warehouse Multiretailer Problem.

Retsef Levi, Robin Roundy, David B. Shmoys, Maxim Sviridenko

Manag. Sci., 2008

Approximation Algorithms for Capacitated Stochastic Inventory Control Models.

Retsef Levi, Robin Roundy, David B. Shmoys, Van-Anh Truong

Oper. Res., 2008

A Constant Approximation Algorithm for the a prioriTraveling Salesman Problem.

David B. Shmoys, Kunal Talwar

Proceedings of the Integer Programming and Combinatorial Optimization, 2008

2007

Provably Near-Optimal Sampling-Based Policies for Stochastic Inventory Control Models.

Retsef Levi, Robin Roundy, David B. Shmoys

Math. Oper. Res., 2007

Approximation Algorithms for Stochastic Inventory Control Models.

Retsef Levi, Martin Pál, Robin Roundy, David B. Shmoys

Math. Oper. Res., 2007

Approximation Algorithms for 2-Stage Stochastic Scheduling Problems.

David B. Shmoys, Mauro Sozio

Proceedings of the Integer Programming and Combinatorial Optimization, 2007

Sampling-based Approximation Algorithms for Multi-stage Stochastic Optimization.

Chaitanya Swamy, David B. Shmoys

Proceedings of the Probabilistic Methods in the Design and Analysis of Algorithms, 23.09., 2007

2006

Approximation algorithms for 2-stage stochastic optimization problems.

Chaitanya Swamy, David B. Shmoys

SIGACT News, 2006

Primal-Dual Algorithms for Deterministic Inventory Problems.

Retsef Levi, Robin Roundy, David B. Shmoys

Math. Oper. Res., 2006

An approximation scheme for stochastic linear programming and its application to stochastic integer programs.

David B. Shmoys, Chaitanya Swamy

J. ACM, 2006

Provably near-optimal sampling-based algorithms for Stochastic inventory control models.

Retsef Levi, Robin Roundy, David B. Shmoys

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

2005

The MSOM Society Student Paper Competition: Extended Abstracts of 2004 Winners.

Retsef Levi, Martin Pál, Robin O. Roundy, David B. Shmoys, Ravi Subramanian, Xinxin Hu, Gad Allon, Felipe Caro, Holly S. Lutze

Manuf. Serv. Oper. Manag., 2005

A constant approximation algorithm for the one-warehouse multi-retailer problem.

Retsef Levi, Robin Roundy, David B. Shmoys

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Inventory and Facility Location Models with Market Selection.

Retsef Levi, Joseph Geunes, H. Edwin Romeijn, David B. Shmoys

Proceedings of the Integer Programming and Combinatorial Optimization, 2005

Sampling-based Approximation Algorithms for Multi-stage Stochastic.

Chaitanya Swamy, David B. Shmoys

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.

Chaitanya Swamy, David B. Shmoys

Proceedings of the Algorithms for Optimization with Incomplete Information, 2005

2004

An improved approximation algorithm for the partial Latin square extension problem.

Carla P. Gomes, Rommel G. Regis, David B. Shmoys

Oper. Res. Lett., 2004

Foreword.

David B. Shmoys

J. Algorithms, 2004

Approximations and Randomization to Boost CSP Techniques.

Carla P. Gomes, David B. Shmoys

Ann. Oper. Res., 2004

Facility location with Service Installation Costs.

David B. Shmoys, Chaitanya Swamy, Retsef Levi

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Stochastic Optimization is (Almost) as easy as Deterministic Optimization.

David B. Shmoys, Chaitanya Swamy

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003

Improved Approximation Algorithms for the Uncapacitated Facility Location Problem.

Fabián A. Chudak, David B. Shmoys

SIAM J. Comput., 2003

Lagrangian Relaxation for the k-Median Problem: New Insights and Continuity Properties.

Aaron Archer, Ranjithkumar Rajagopalan, David B. Shmoys

Proceedings of the Algorithms, 2003

2002

A Constant-Factor Approximation Algorithm for the k-Median Problem.

Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys

J. Comput. Syst. Sci., 2002

2000

Approximation algorithms for facility location problems.

David B. Shmoys

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.

Fabián A. Chudak, David B. Shmoys

J. Algorithms, 1999

A 3-Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem.

Karen I. Aardal, Fabián A. Chudak, David B. Shmoys

Inf. Process. Lett., 1999

A Constant-Factor Approximation Algorithm for the <i>k</i>-Median Problem (Extended Abstract).

Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Improved Approximation Algorithms for a Capacitated Facility Location Problem.

Fabián A. Chudak, David B. Shmoys

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Approximation Algorithms for Clustering Problems.

David B. Shmoys

Proceedings of the Twelfth Annual Conference on Computational Learning Theory, 1999

1998

Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem.

Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Clifford Stein, Joel Wein

J. Comb. Optim., 1998

Using Linear Programming in the Design and Analysis of Approximation Algorithms: Two Illustrative Problems.

David B. Shmoys

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 1998

1997

Strategic directions in research in theory of computing.

Anne Condon, Faith E. Fich, Greg N. Frederickson, Andrew V. Goldberg, David S. Johnson, Michael C. Loui, Steven Mahaney, Prabhakar Raghavan, John E. Savage, Alan L. Selman, David B. Shmoys

SIGACT News, 1997

Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms.

Leslie A. Hall, Andreas S. Schulz, David B. Shmoys, Joel Wein

Math. Oper. Res., 1997

Short Shop Schedules.

David P. Williamson, Leslie A. Hall, J. A. Hoogeveen, Cor A. J. Hurkens, Jan Karel Lenstra, Sergey Vasil'evich Sevast'janov, David B. Shmoys

Oper. Res., 1997

Approximation Algorithms for Facility Location Problems (Extended Abstract).

David B. Shmoys, Éva Tardos, Karen I. Aardal

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

Fabián A. Chudak, David B. Shmoys

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.

Leslie A. Hall, David B. Shmoys, Joel Wein

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.

Paul Martin, David B. Shmoys

Proceedings of the Integer Programming and Combinatorial Optimization, 1996

Improved Scheduling Algorithms for Minsum Criteria.

Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Clifford Stein, Joel Wein

Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

1995

Scheduling Parallel Machines On-Line.

David B. Shmoys, Joel Wein, David P. Williamson

SIAM J. Comput., 1995

Fast Approximation Algorithms for Fractional Packing and Covering Problems.

Serge A. Plotkin, David B. Shmoys, Éva Tardos

Math. Oper. Res., 1995

1994

Improved Approximation Algorithms for Shop Scheduling Problems.

David B. Shmoys, Clifford Stein, Joel Wein

SIAM J. Comput., 1994

Improved Approximation Algorithms for Network Design Problems.

Michel X. Goemans, Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos, David P. Williamson

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.

David B. Shmoys, Éva Tardos

Math. Program., 1993

Scheduling Unrelated Machines with Costs.

David B. Shmoys, Éva Tardos

Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

Computing near-optimal solutions to combinatorial optimization problems.

David B. Shmoys

Proceedings of the Combinatorial Optimization, 1993

Chapter 9 Sequencing and scheduling: Algorithms and complexity.

Eugene L. Lawler, Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, David B. Shmoys

Proceedings of the Logistics of Production and Inventory, 1993

1992

Using Interior-Point Methods for Fast Parallel Algorithms for Bipartite Matching and Related Problems.

Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos

SIAM J. Comput., 1992

Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better.

Leslie A. Hall, David B. Shmoys

Math. Oper. Res., 1992

1991

Permutation vs. non-permutation flow shop schedules.

Chris N. Potts, David B. Shmoys, David P. Williamson

Oper. Res. Lett., 1991

1990

Flipping Persuasively in Constant Time.

Cynthia Dwork, David B. Shmoys, Larry J. Stockmeyer

SIAM J. Comput., 1990

Approximation Algorithms for Scheduling Unrelated Parallel Machines.

Jan Karel Lenstra, David B. Shmoys, Éva Tardos

Math. Program., 1990

Analyzing the Held-Karp TSP Bound: A Monotonicity Property with Application.

David B. Shmoys, David P. Williamson

Inf. Process. Lett., 1990

Near-Optimal Sequencing with Precedence Constraints.

Leslie A. Hall, David B. Shmoys

Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, 1990

1989

The Parallel Complexity of TSP Heuristics.

Gerard A. P. Kindervater, Jan Karel Lenstra, David B. Shmoys

J. Algorithms, 1989

Simple constant-time consensus protocols in realistic failure models.

Benny Chor, Michael Merritt, David B. Shmoys

J. ACM, 1989

Approximation Schemes for Constrained Scheduling Problems

Leslie A. Hall, David B. Shmoys

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

Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos

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.

Dorit S. Hochbaum, David B. Shmoys

SIAM J. Comput., 1988

1987

Efficient Parallel Algorithms for Edge Coloring Problems.

Howard J. Karloff, David B. Shmoys

J. Algorithms, 1987

Using dual approximation algorithms for scheduling problems theoretical and practical results.

Dorit S. Hochbaum, David B. Shmoys

J. ACM, 1987

1986

A Better than "Best Possible" Algorithm to Edge Color Multigraphs.

Dorit S. Hochbaum, Takao Nishizeki, David B. Shmoys

J. Algorithms, 1986

A unified approach to approximation algorithms for bottleneck problems.

Dorit S. Hochbaum, David B. Shmoys

J. ACM, 1986

A Polynomial Approximation Scheme for Machine Scheduling on Uniform Processors: Using the Dual Approximation Approach.

Dorit S. Hochbaum, David B. Shmoys

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1986

Flipping Persuasively in Constant Expected Time (Preliminary Version)

Cynthia Dwork, David B. Shmoys, Larry J. Stockmeyer

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985

A Best Possible Heuristic for the <i>k</i>-Center Problem.

Dorit S. Hochbaum, David B. Shmoys

Math. Oper. Res., 1985

Simple Constant-Time Consensus Protocols in Realistic Failure Models (Extended Abstract).

Benny Chor, Michael Merritt, David B. Shmoys

Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, 1985

1984

Recognizing graphs with fixed interval number is NP-complete.

Douglas B. West, David B. Shmoys

Discret. Appl. Math., 1984

Powers of Graphs: A Powerful Approximation Technique for Bottleneck Problems

Dorit S. Hochbaum, David B. Shmoys

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984