David B. Shmoys

Retsef Levi, David B. Shmoys, Chaitanya Swamy: LP-based approximation algorithms for capacitated facility location. Math. Program. 131(1-2): 365-379 (2012)

Chaitanya Swamy, David B. Shmoys: Sampling-Based Approximation Algorithms for Multistage Stochastic Optimization. SIAM J. Comput. 41(4): 975-1004 (2012)

Hyung-Chan An, Robert Kleinberg, David B. Shmoys: Improving christofides' algorithm for the s-t path TSP. STOC 2012: 875-886

Daniel Sheldon, Bistra N. Dilkina, Adam N. Elmachtoub, Ryan Finseth, Ashish Sabharwal, Jon Conrad, Carla P. Gomes, David B. Shmoys, William Allen, Ole Amundsen, William Vaughan: Maximizing the Spread of Cascades Using Network Design. CoRR abs/1203.3514 (2012)

David P. Williamson, David B. Shmoys: The Design of Approximation Algorithms. Cambridge University Press 2011, isbn 978-0-521-19527-0, pp. I-XI, 1-504

Joseph Geunes, Retsef Levi, H. Edwin Romeijn, David B. Shmoys: Approximation algorithms for supply chain planning and logistics problems with market choice. Math. Program. 130(1): 85-106 (2011)

Tim Carnes, David B. Shmoys: Primal-Dual Schema and Lagrangian Relaxation for the k-Location-Routing Problem. APPROX-RANDOM 2011: 99-110

Maurice Cheung, David B. Shmoys: A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems. APPROX-RANDOM 2011: 135-146

David B. Shmoys, Gwen Spencer: Approximation Algorithms for Fragmenting a Graph against a Stochastically-Located Threat. WAOA 2011: 123-136

Hyung-Chan An, David B. Shmoys: LP-Based Approximation Algorithms for Traveling Salesman Path Problems. CoRR abs/1105.2391 (2011)

Hyung-Chan An, Robert Kleinberg, David B. Shmoys: Improving Christofides' Algorithm for the s-t Path TSP. CoRR abs/1110.4604 (2011)

Paat Rusmevichientong, Zuo-Jun Max Shen, David B. Shmoys: Dynamic Assortment Optimization with a Multinomial Logit Choice Model and Capacity Constraint. Operations Research 58(6): 1666-1680 (2010)

Hyung-Chan An, Robert D. Kleinberg, David B. Shmoys: Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem. APPROX-RANDOM 2010: 1-11

Igor Gorodezky, Robert D. Kleinberg, David B. Shmoys, Gwen Spencer: Improved Lower Bounds for the Universal and a priori TSP. APPROX-RANDOM 2010: 178-191

Daniel Sheldon, Bistra N. Dilkina, Adam N. Elmachtoub, Ryan Finseth, Ashish Sabharwal, Jon Conrad, Carla P. Gomes, David B. Shmoys, William Allen, Ole Amundsen, William Vaughan: Maximizing the Spread of Cascades Using Network Design. UAI 2010: 517-526

Paat Rusmevichientong, Zuo-Jun Max Shen, David B. Shmoys: A PTAS for capacitated sum-of-ratios optimization. Oper. Res. Lett. 37(4): 230-238 (2009)

Retsef Levi, Robin Roundy, David B. Shmoys, Van Anh Truong: Approximation Algorithms for Capacitated Stochastic Inventory Control Models. Operations Research 56(5): 1184-1199 (2008)

Retsef Levi, Robin Roundy, David B. Shmoys, Maxim Sviridenko: A Constant Approximation Algorithm for the One-Warehouse Multiretailer Problem. Management Science 54(4): 763-776 (2008)

Frans Schalekamp, David B. Shmoys: Algorithms for the universal and a priori TSP. Oper. Res. Lett. 36(1): 1-3 (2008)

Chaitanya Swamy, David B. Shmoys: Fault-tolerant facility location. ACM Transactions on Algorithms 4(4) (2008)

Tim Carnes, David B. Shmoys: Primal-Dual Schema for Capacitated Covering Problems. IPCO 2008: 288-302

David B. Shmoys, Kunal Talwar: A Constant Approximation Algorithm for the a prioriTraveling Salesman Problem. IPCO 2008: 331-343

Retsef Levi, Martin Pál, Robin Roundy, David B. Shmoys: Approximation Algorithms for Stochastic Inventory Control Models. Math. Oper. Res. 32(2): 284-302 (2007)

Retsef Levi, Robin Roundy, David B. Shmoys: Provably Near-Optimal Sampling-Based Policies for Stochastic Inventory Control Models. Math. Oper. Res. 32(4): 821-839 (2007)

Chaitanya Swamy, David B. Shmoys: Sampling-based Approximation Algorithms for Multi-stage Stochastic Optimization. Probabilistic Methods in the Design and Analysis of Algorithms 2007

David B. Shmoys, Mauro Sozio: Approximation Algorithms for 2-Stage Stochastic Scheduling Problems. IPCO 2007: 145-157

David B. Shmoys, Chaitanya Swamy: An approximation scheme for stochastic linear programming and its application to stochastic integer programs. J. ACM 53(6): 978-1012 (2006)

Retsef Levi, Robin Roundy, David B. Shmoys: Primal-Dual Algorithms for Deterministic Inventory Problems. Math. Oper. Res. 31(2): 267-284 (2006)

Chaitanya Swamy, David B. Shmoys: Approximation algorithms for 2-stage stochastic optimization problems. SIGACT News 37(1): 33-46 (2006)

Chaitanya Swamy, David B. Shmoys: Approximation Algorithms for 2-Stage Stochastic Optimization Problems. FSTTCS 2006: 5-19

Retsef Levi, Robin Roundy, David B. Shmoys: Provably near-optimal sampling-based algorithms for Stochastic inventory control models. STOC 2006: 739-748

Chaitanya Swamy, David B. Shmoys: Approximation Algorithms for 2-stage and Multi-stage Stochastic Optimization. Algorithms for Optimization with Incomplete Information 2005

Chaitanya Swamy, David B. Shmoys: Sampling-based Approximation Algorithms for Multi-stage Stochastic. FOCS 2005: 357-366

Retsef Levi, Joseph Geunes, H. Edwin Romeijn, David B. Shmoys: Inventory and Facility Location Models with Market Selection. IPCO 2005: 111-124

Retsef Levi, Martin Pál, Robin Roundy, David B. Shmoys: Approximation Algorithms for Stochastic Inventory Control Models. IPCO 2005: 306-320

Retsef Levi, Robin Roundy, David B. Shmoys: A constant approximation algorithm for the one-warehouse multi-retailer problem. SODA 2005: 365-374

Carla P. Gomes, David B. Shmoys: Approximations and Randomization to Boost CSP Techniques. Annals OR 130(1-4): 117-141 (2004)

David B. Shmoys: Foreword. J. Algorithms 50(2): 133 (2004)

Carla P. Gomes, Rommel G. Regis, David B. Shmoys: An improved approximation algorithm for the partial Latin square extension problem. Oper. Res. Lett. 32(5): 479-484 (2004)

David B. Shmoys, Chaitanya Swamy: Stochastic Optimization is (Almost) as easy as Deterministic Optimization. FOCS 2004: 228-237

Retsef Levi, David B. Shmoys, Chaitanya Swamy: LP-based Approximation Algorithms for Capacitated Facility Location. IPCO 2004: 206-218

David B. Shmoys, Chaitanya Swamy, Retsef Levi: Facility location with Service Installation Costs. SODA 2004: 1088-1097

Retsef Levi, Robin Roundy, David B. Shmoys: Primal-dual algorithms for deterministic inventory problems. STOC 2004: 353-362

Fabián A. Chudak, David B. Shmoys: Improved Approximation Algorithms for the Uncapacitated Facility Location Problem. SIAM J. Comput. 33(1): 1-25 (2003)

Aaron Archer, Ranjithkumar Rajagopalan, David B. Shmoys: Lagrangian Relaxation for the k-Median Problem: New Insights and Continuity Properties. ESA 2003: 31-42

Chaitanya Swamy, David B. Shmoys: Fault-tolerant facility location. SODA 2003: 735-736

Carla P. Gomes, Rommel G. Regis, David B. Shmoys: An improved approximation algorithm for the partial latin square extension problem. SODA 2003: 832-833

Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys: A Constant-Factor Approximation Algorithm for the k-Median Problem. J. Comput. Syst. Sci. 65(1): 129-149 (2002)

David B. Shmoys: Approximation algorithms for facility location problems. APPROX 2000: 27-33

David B. Shmoys (Ed.): Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, January 9-11, 2000, San Francisco, CA, USA. ACM/SIAM 2000, isbn 0-89871-453-2

Karen Aardal, Fabián A. Chudak, David B. Shmoys: A 3-Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem. Inf. Process. Lett. 72(5-6): 161-167 (1999)

Fabián A. Chudak, David B. Shmoys: Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds. J. Algorithms 30(2): 323-343 (1999)

David B. Shmoys: Approximation Algorithms for Clustering Problems. COLT 1999: 100-102

Fabián A. Chudak, David B. Shmoys: Improved Approximation Algorithms for a Capacitated Facility Location Problem. SODA 1999: 875-876

Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys: A Constant-Factor Approximation Algorithm for the k-Median Problem (Extended Abstract). STOC 1999: 1-10

Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Clifford Stein, Joel Wein: Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem. J. Comb. Optim. 1(4): 413-426 (1998)

David B. Shmoys: Using Linear Programming in the Design and Analysis of Approximation Algorithms: Two Illustrative Problems. APPROX 1998: 15-32

Anne Condon, Faith 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: Strategic directions in research in theory of computing. SIGACT News 28(3): 75-93 (1997)

Fabián A. Chudak, David B. Shmoys: Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines That Run at Fifferent Speeds (Extended Abstract). SODA 1997: 581-590

David B. Shmoys, Éva Tardos, Karen Aardal: Approximation Algorithms for Facility Location Problems (Extended Abstract). STOC 1997: 265-274

Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Clifford Stein, Joel Wein: Improved Scheduling Algorithms for Minsum Criteria. ICALP 1996: 646-657

Paul Martin, David B. Shmoys: A New Approach to Computing Optimal Schedules for the Job-Shop Scheduling Problem. IPCO 1996: 389-403

Leslie A. Hall, David B. Shmoys, Joel Wein: Scheduling to Minimize Average Completion Time: Off-line and On-line Algorithms. SODA 1996: 142-151

David B. Shmoys, Joel Wein, David P. Williamson: Scheduling Parallel Machines On-Line. SIAM J. Comput. 24(6): 1313-1331 (1995)

David B. Shmoys, Clifford Stein, Joel Wein: Improved Approximation Algorithms for Shop Scheduling Problems. SIAM J. Comput. 23(3): 617-632 (1994)

Michel X. Goemans, Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos, David P. Williamson: Improved Approximation Algorithms for Network Design Problems. SODA 1994: 223-232

David B. Shmoys, Éva Tardos: An approximation algorithm for the generalized assignment problem. Math. Program. 62: 461-474 (1993)

David B. Shmoys, Éva Tardos: Scheduling Unrelated Machines with Costs. SODA 1993: 448-454

Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos: Using Interior-Point Methods for Fast Parallel Algorithms for Bipartite Matching and Related Problems. SIAM J. Comput. 21(1): 140-150 (1992)

David B. Shmoys, Joel Wein, David P. Williamson: Scheduling Parallel Machines On-Line. FOCS 1991: 131-140

Serge A. Plotkin, David B. Shmoys, Éva Tardos: Fast Approximation Algorithms for Fractional Packing and Covering Problems. FOCS 1991: 495-504

David B. Shmoys, Clifford Stein, Joel Wein: Improved Approximation Algorithms for Shop Scheduling Problems. SODA 1991: 148-157

David B. Shmoys, David P. Williamson: Analyzing the Held-Karp TSP Bound: A Monotonicity Property with Application. Inf. Process. Lett. 35(6): 281-285 (1990)

Jan Karel Lenstra, David B. Shmoys, Éva Tardos: Approximation Algorithms for Scheduling Unrelated Parallel Machines. Math. Program. 46: 259-271 (1990)

Cynthia Dwork, David B. Shmoys, Larry J. Stockmeyer: Flipping Persuasively in Constant Time. SIAM J. Comput. 19(3): 472-499 (1990)

Leslie A. Hall, David B. Shmoys: Near-Optimal Sequencing with Precedence Constraints. IPCO 1990: 249-260

Benny Chor, Michael Merritt, David B. Shmoys: Simple constant-time consensus protocols in realistic failure models. J. ACM 36(3): 591-614 (1989)

Gerard A. P. Kindervater, Jan Karel Lenstra, David B. Shmoys: The Parallel Complexity of TSP Heuristics. J. Algorithms 10(2): 249-270 (1989)

Leslie A. Hall, David B. Shmoys: Approximation Schemes for Constrained Scheduling Problems. FOCS 1989: 134-139

Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos: Interior-Point Methods in Parallel Computation. FOCS 1989: 350-355

Dorit S. Hochbaum, David B. Shmoys: A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach. SIAM J. Comput. 17(3): 539-551 (1988)

Dorit S. Hochbaum, David B. Shmoys: Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM 34(1): 144-162 (1987)

Howard J. Karloff, David B. Shmoys: Efficient Parallel Algorithms for Edge Coloring Problems. J. Algorithms 8(1): 39-52 (1987)

Jan Karel Lenstra, David B. Shmoys, Éva Tardos: Approximation Algorithms for Scheduling Unrelated Parallel Machines. FOCS 1987: 217-224

Dorit S. Hochbaum, David B. Shmoys: A unified approach to approximation algorithms for bottleneck problems. J. ACM 33(3): 533-550 (1986)

Dorit S. Hochbaum, Takao Nishizeki, David B. Shmoys: A Better than "Best Possible" Algorithm to Edge Color Multigraphs. J. Algorithms 7(1): 79-104 (1986)

Cynthia Dwork, David B. Shmoys, Larry J. Stockmeyer: Flipping Persuasively in Constant Expected Time (Preliminary Version). FOCS 1986: 222-232

Dorit S. Hochbaum, David B. Shmoys: A Polynomial Approximation Scheme for Machine Scheduling on Uniform Processors: Using the Dual Approximation Approach. FSTTCS 1986: 382-393

Dorit S. Hochbaum, David B. Shmoys: Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results. FOCS 1985: 79-89

Benny Chor, Michael Merritt, David B. Shmoys: Simple Constant-Time Consensus Protocols in Realistic Failure Models (Extended Abstract). PODC 1985: 152-162

Dorit S. Hochbaum, David B. Shmoys: Powers of Graphs: A Powerful Approximation Technique for Bottleneck Problems. STOC 1984: 324-333