David B. Shmoys - Publications

Affiliations: 
Operations Research and Information Engineering Cornell University, Ithaca, NY, United States 
Area:
Optimization, Algorithms, Data Science, Approximation Algorithms
Website:
https://www.orie.cornell.edu/faculty-directory/david-b-shmoys

65/93 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2018 Freund D, Henderson SG, Shmoys DB. Minimizing Multimodular Functions and Allocating Capacity in Bike-Sharing Systems Production and Operations Management. 27: 2346-2349. DOI: 10.1111/Poms.12965  0.339
2018 Steele PR, Henderson SG, Shmoys DB. Aggregating courier deliveries Naval Research Logistics (Nrl). 65: 187-202. DOI: 10.1002/Nav.21804  0.402
2017 Cheung M, Mestre J, Shmoys DB, Verschae J. A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems Siam Journal On Discrete Mathematics. 31: 825-838. DOI: 10.1137/16M1086819  0.362
2016 Cheung M, Elmachtoub AN, Levi R, Shmoys DB. The submodular joint replenishment problem Mathematical Programming. 158: 207-233. DOI: 10.1007/S10107-015-0920-3  0.634
2015 Shmoys DB, Spencer G. Approximation Algorithms for Fragmenting a Graph Against a Stochastically-Located Threat Theory of Computing Systems \/ Mathematical Systems Theory. 56: 96-134. DOI: 10.1007/S00224-014-9548-6  0.696
2015 O'Mahony E, Shmoys DB. Data analysis and optimization for (Citi)bike sharing Proceedings of the National Conference On Artificial Intelligence. 1: 687-694.  0.312
2014 Macdonald RD, Ahghari M, Walker L, Carnes TA, Henderson SG, Shmoys DB. A novel application to optimize utilization for nonurgent air transfers. Air Medical Journal. 33: 34-9. PMID 24373475 DOI: 10.1016/J.Amj.2013.09.004  0.707
2014 Rusmevichientong P, Shmoys D, Tong C, Topaloglu H. Assortment optimization under the multinomial logit model with random choice parameters Production and Operations Management. 23: 2023-2039. DOI: 10.1111/Poms.12191  0.399
2013 Carnes TA, Henderson SG, Shmoys DB, Ahghari M, MacDonald RD. Mathematical programming guides air-ambulance routing at ornge Interfaces. 43: 232-239. DOI: 10.1287/Inte.2013.0683  0.73
2012 An HC, Kleinberg R, Shmoys DB. Improving Christofides' algorithm for the s-t path TSP Proceedings of the Annual Acm Symposium On Theory of Computing. 875-885. DOI: 10.1145/2818310  0.735
2012 Swamy C, Shmoys DB. Sampling-based approximation algorithms for multistage stochastic optimization Siam Journal On Computing. 41: 975-1004. DOI: 10.1137/100789269  0.652
2012 Levi R, Shmoys DB, Swamy C. LP-based approximation algorithms for capacitated facility location Mathematical Programming. 131: 365-379. DOI: 10.1007/S10107-010-0380-8  0.732
2012 Shmoys DB, Spencer G. Approximation algorithms for fragmenting a graph against a stochastically-located threat Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7164: 123-136. DOI: 10.1007/978-3-642-29116-6_11  0.377
2011 Williamson DP, Shmoys DB. The design of approximation algorithms The Design of Approximation Algorithms. 1-504. DOI: 10.1017/CBO9780511921735  0.399
2011 Geunes J, Levi R, Romeijn HE, Shmoys DB. Approximation algorithms for supply chain planning and logistics problems with market choice Mathematical Programming. 130: 85-106. DOI: 10.1007/S10107-009-0310-9  0.576
2011 Carnes T, Shmoys DB. Primal-dual schema and Lagrangian relaxation for the k-location-routing problem Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6845: 99-110. DOI: 10.1007/978-3-642-22935-0_9  0.398
2011 Cheung M, Shmoys DB. A primal-dual approximation algorithm for min-sum single-machine scheduling problems Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6845: 135-146. DOI: 10.1007/978-3-642-22935-0_12  0.406
2010 Rusmevichientong P, Shen ZJM, Shmoys DB. Dynamic assortment optimization with a multinomial logit choice model and capacity constraint Operations Research. 58: 1666-1680. DOI: 10.1287/Opre.1100.0866  0.352
2010 An HC, Kleinberg RD, Shmoys DB. Approximation algorithms for the bottleneck asymmetric traveling salesman problem Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6302: 1-11. DOI: 10.1007/978-3-642-15369-3_1  0.742
2008 Levi R, Roundy RO, Shmoys DB, Van Truong A. Approximation algorithms for capacitated stochastic inventory control models Operations Research. 56: 1184-1199. DOI: 10.1287/Opre.1080.0580  0.587
2008 Swamy C, Shmoys DB. Fault-tolerant facility location Acm Transactions On Algorithms. 4. DOI: 10.1145/1383369.1383382  0.591
2008 Schalekamp F, Shmoys DB. Algorithms for the universal and a priori TSP Operations Research Letters. 36: 1-3. DOI: 10.1016/j.orl.2007.04.009  0.315
2008 Shmoys D, Talwar K. A constant approximation algorithm for the a priori traveling salesman problem Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5035: 331-343. DOI: 10.1007/978-3-540-68891-4_23  0.362
2008 Carnes T, Shmoys D. Primal-dual schema for capacitated covering problems Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5035: 288-302. DOI: 10.1007/978-3-540-68891-4_20  0.311
2007 Levi R, Roundy RO, Shmoys DB. Provably near-optimal sampling-based policies for stochastic inventory control models Mathematics of Operations Research. 32: 821-839. DOI: 10.1287/Moor.1070.0272  0.571
2007 Shmoys DB, Sozio M. Approximation algorithms for 2-stage stochastic scheduling problems Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4513: 145-157.  0.378
2006 Shmoys DB, Swamy C. An approximation scheme for stochastic linear programming and its application to stochastic integer programs Journal of the Acm. 53: 978-1012. DOI: 10.1145/1217856.1217860  0.653
2006 Swamy C, Shmoys DB. Approximation algorithms for 2-stage stochastic optimization problems Sigact News. 37: 33-46. DOI: 10.1145/1122480.1122493  0.644
2006 Levi R, Roundy RO, Shmoys DB. Provably near-optimal sampling-based algorithms for stochastic Inventory control models Proceedings of the Annual Acm Symposium On Theory of Computing. 2006: 739-748.  0.594
2005 Levi R, Pál M, Roundy RO, Shmoys DB, Subramanian R, Hu X, Allon G, Caro F, Lutze HS. The MSOM Society Student Paper Competition: Extended Abstracts of 2004 Winners Manufacturing & Service Operations Management. 7: 81-99. DOI: 10.1287/Msom.1050.0075  0.43
2005 Levi R, Pál M, Roundy R, Shmoys DB. Approximation algorithms for stochastic inventory control models Lecture Notes in Computer Science. 3509: 306-320. DOI: 10.1287/Moor.1060.0205  0.649
2005 Levi R, Roundy R, Shmoys DB. A constant approximation algorithm for the one-warehouse multi-retailer problem Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 365-374. DOI: 10.1287/Mnsc.1070.0781  0.665
2005 Swamy C, Shmoys DB. Sampling-based approximation algorithms for multi-stage stochastic optimization Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 2005: 357-366. DOI: 10.1109/SFCS.2005.67  0.618
2005 Levi R, Geunes J, Romeijn HE, Shmoys DB. Inventory and facility location models with market selection Lecture Notes in Computer Science. 3509: 111-124.  0.525
2004 Levi R, Roundy R, Shmoys DB. Primal-dual algorithms for deterministic inventory problems Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 353-362. DOI: 10.1287/Moor.1050.0178  0.643
2004 Gomes CP, Regis RG, Shmoys DB. An improved approximation algorithm for the partial Latin square extension problem Operations Research Letters. 32: 479-484. DOI: 10.1016/J.Orl.2003.09.007  0.332
2004 Shmoys DB, Swamy C, Levi R. Facility Location with Service Installation Costs Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 15: 1081-1090.  0.594
2004 Shmoys DB, Swamy C. Stochastic optimization is (almost) as easy as deterministic optimization Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 228-237.  0.567
2003 Chudak FA, Shmoys DB. Improved approximation algorithms for the uncapacitated facility location problem Siam Journal On Computing. 33: 1-25. DOI: 10.1137/S0097539703405754  0.448
2000 Shmoys DB. Approximation algorithms for facility location problems Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1913: 27-32.  0.359
1999 Aardal K, Chudak FA, Shmoys DB. A 3-approximation algorithm for the k-level uncapacitated facility location problem Information Processing Letters. 72: 161-167.  0.393
1998 Phillips CA, Schulz AS, Shmoys DB, Stein C, Wein J. Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem Journal of Combinatorial Optimization. 1: 413-426. DOI: 10.1023/A:1009750913529  0.492
1998 Shmoys DB. Using linear programming in the design and analysis of approximation algorithms: Two illustrative problems Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1444: 15-32. DOI: 10.1007/BFb0053960  0.384
1998 Phillips CA, Schulz AS, Shmoys DB, Stein C, Wein J. Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem Journal of Combinatorial Optimization. 1: 413-426.  0.305
1997 Schulz AS, Shmoys DB, Williamson DP. Approximation algorithms. Proceedings of the National Academy of Sciences of the United States of America. 94: 12734-5. PMID 9370525 DOI: 10.1073/pnas.94.24.12734  0.378
1997 Williamson DP, Hall LA, Hoogeveen JA, Hurkens CAJ, Lenstra JK, Sevast'janov SV, Shmoys DB. Short shop schedules Operations Research. 45: 288-294.  0.35
1997 Hall LA, Schulz AS, Shmoys DB, Wein J. Scheduling to minimize average completion time: Off-line and on-line approximation algorithms Mathematics of Operations Research. 22: 513-544.  0.35
1996 Chakrabarti S, Phillips CA, Schulz AS, Shmoys DB, Stein C, Wein J. Improved scheduling algorithms for minsum criteria Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1099: 646-657.  0.341
1996 Martin P, Shmoys DB. A new approach to computing optimal schedules for the job-shop scheduling problem Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1084: 389-403.  0.338
1995 Plotkin SA, Shmoys DB, Tardos É. Fast approximation algorithms for fractional packing and covering problems Mathematics of Operations Research. 20: 257-301. DOI: 10.1287/Moor.20.2.257  0.406
1994 Shmoys DB, Stein C, Wein J. Improved Approximation Algorithms for Shop Scheduling Problems Siam Journal On Computing. 23: 617-632. DOI: 10.1137/S009753979222676X  0.497
1994 Gustfield D, Shmoys D, Lenstra JK, Warnow T. In Memoriam Eugene L. Lawler Journal of Computational Biology. 1: 255-256. DOI: 10.1089/Cmb.1994.1.255  0.467
1994 Goemans MX, Goldberg AV, Plotkin S, Shmoys DB, Tardos E, Williamson DP. Improved approximation algorithms for network design problems Proceedings of the Annual Acm Siam Symposium On Discrete Algorithms. 223-232.  0.339
1993 Shmoys DB, Tardos E. An approximation algorithm for the generalized assignment problem Mathematical Programming. 62: 461-474. DOI: 10.1007/Bf01585178  0.335
1992 Goldberg AV, Plotkin SA, Shmoys DB, Tardos É. Using interior-point methods for fast parallel algorithms for bipartite matching and related problems Siam Journal On Computing. 21: 140-150. DOI: 10.1137/0221011  0.369
1990 Shmoys DB, Williamson DP. Analyzing the Held-Karp tsp bound: a monotonicity property with application Information Processing Letters. 35: 281-285. DOI: 10.1016/0020-0190(90)90028-V  0.327
1990 Lenstra JK, Shmoys DB, Tardos E. Approximation algorithms for scheduling unrelated parallel machines Mathematical Programming. 46: 259-271. DOI: 10.1007/Bf01585745  0.312
1988 Hochbaum Ds, Shmoys DB. A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach Siam Journal On Computing. 17: 539-551. DOI: 10.1137/0217033  0.34
1987 Hochbaum DS, Shmoys DB. Using dual approximation algorithms for scheduling problems theoretical and practical results Journal of the Acm (Jacm). 34: 144-162. DOI: 10.1145/7531.7535  0.372
1987 Karloff HJ, Shmoys DB. Efficient parallel algorithms for edge coloring problems Journal of Algorithms. 8: 39-52. DOI: 10.1016/0196-6774(87)90026-5  0.311
1986 Hochbaum DS, Shmoys DB. A unified approach to approximation algorithms for bottleneck problems Journal of the Acm (Jacm). 33: 533-550. DOI: 10.1145/5925.5933  0.358
1986 Hochbaum DS, Shmoys DB. A packing problem you can almost solve by sitting on your suitcase Siam Journal On Algebraic and Discrete Methods. 7: 247-257. DOI: 10.1137/0607028  0.389
1986 Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB. Erratum: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization Journal of the Operational Research Society. 37: 655-655. DOI: 10.1057/jors.1986.117  0.327
1986 Hochbaum DS, Shmoys DB. Best possible heuristics for the bottleneck wandering salesperson and bottleneck vehicle routing problem European Journal of Operational Research. 26: 380-384. DOI: 10.1016/0377-2217(86)90140-2  0.32
1985 Hochbaum DS, Shmoys DB. A Best Possible Heuristic for the k-Center Problem Mathematics of Operations Research. 10: 180-184. DOI: 10.1287/Moor.10.2.180  0.332
Low-probability matches (unlikely to be authored by this person)
1999 Chudak FA, Shmoys DB. Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds Journal of Algorithms. 30: 323-343.  0.295
1989 Kindervater GAP, Lenstra JK, Shmoys DB. The parallel complexity of TSP heuristics Journal of Algorithms. 10: 249-270. DOI: 10.1016/0196-6774(89)90015-1  0.294
2010 Gorodezky I, Kleinberg RD, Shmoys DB, Spencer G. Improved lower bounds for the universal and a priori TSP Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6302: 178-191. DOI: 10.1007/978-3-642-15369-3_14  0.283
2009 Rusmevichientong P, Max Shen ZJ, Shmoys DB. A PTAS for capacitated sum-of-ratios optimization Operations Research Letters. 37: 230-238. DOI: 10.1016/J.Orl.2009.03.009  0.28
2003 Charikar M, Guha S, Tardos E, Shmoys DB. A constant-factor approximation algorithm for the k-median problem Journal of Computer and System Sciences. 65: 129-149. DOI: 10.1006/jcss.2002.1882  0.275
2004 Gomes CP, Shmoys DB. Approximations and randomization to boost CSP techniques Annals of Operations Research. 130: 117-141. DOI: 10.1023/B:Anor.0000032572.32788.Da  0.263
2016 Lenstra JK, Shmoys D. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation Notices of the American Mathematical Society. 63: 635-638. DOI: 10.1090/Noti1397  0.26
1991 Potts CN, Shmoys DB, Williamson DP. Permutation vs. non-permutation flow shop schedules Operations Research Letters. 10: 281-284. DOI: 10.1016/0167-6377(91)90014-G  0.257
1986 Hochbaum DS, Nishizeki T, Shmoys DB. A better than "best possible" algorithm to edge color multigraphs Journal of Algorithms. 7: 79-104. DOI: 10.1016/0196-6774(86)90039-8  0.253
2020 Paul A, Freund D, Ferber A, Shmoys DB, Williamson DP. Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems Mathematics of Operations Research. 45: 576-590. DOI: 10.1287/moor.2019.1002  0.251
1993 Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB. Chapter 9 Sequencing and scheduling: Algorithms and complexity Handbooks in Operations Research and Management Science. 4: 445-522. DOI: 10.1016/S0927-0507(05)80189-6  0.227
2010 Sheldon D, Dilkina B, Elmachtoub AN, Finseth R, Sabharwal A, Conrad J, Gomes C, Shmoys D, Allen W, Amundsen O, Vaughan W. Maximizing the spread of cascades using network design Proceedings of the 26th Conference On Uncertainty in Artificial Intelligence, Uai 2010. 517-526.  0.222
1985 Hochbaum DS, Shmoys DB. An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem Siam Journal On Algebraic and Discrete Methods. 6: 707-712. DOI: 10.1137/0606068  0.196
1989 Chor B, Merritt M, Shmoys DB. Simple Constant-Time Consensus Protocols in Realistic Failure Models Journal of the Acm (Jacm). 36: 591-614. DOI: 10.1145/65950.65956  0.175
2019 Freund D, Henderson SG, O’Mahony E, Shmoys DB. Analytics and Bikes: Riding Tandem with Motivate to Improve Mobility Informs Journal On Applied Analytics. 49: 310-323. DOI: 10.1287/Inte.2019.1005  0.167
2003 Archer A, Rajagopalan R, Shmoys DB. Lagrangian relaxation for the k-median problem: New insights and continuity properties Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2832: 31-42.  0.158
1992 Hall LA, Shmoys DB. Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better Mathematics of Operations Research. 17: 22-35. DOI: 10.1287/moor.17.1.22  0.133
2011 MacDonald R, Ahghari M, Carnes TA, Henderson SG, Shmoys DB. Use of a Novel Application to Optimize Aircraft Utilization for Non-Urgent Patient Transfers Air Medical Journal. 30: 255. DOI: 10.1016/J.Amj.2011.07.009  0.129
2014 Shmoys D. Foreword Proceedings of the Annual Acm Symposium On Theory of Computing 0.12
1995 Halpern J, Awerbuch B, Benor M, Chandra A, Feigenbaum J, Vonzurgathen J, Guibas L, Pitt L, Saks M, Shmoys D, Sleator D, Upfal E, Vazirani U, Yao A. Editors′ Foreword Journal of Computer and System Sciences. 50: 189. DOI: 10.1006/jcss.1995.1016  0.12
2022 Frazier PI, Cashore JM, Duan N, Henderson SG, Janmohamed A, Liu B, Shmoys DB, Wan J, Zhang Y. Modeling for COVID-19 college reopening decisions: Cornell, a case study. Proceedings of the National Academy of Sciences of the United States of America. 119. PMID 34969678 DOI: 10.1073/pnas.2112532119  0.098
2015 Singhvi D, Singhvi S, Frazier PI, Henderson SG, O'Mahony E, Shmoys DB, Woodard DB. Predicting bike usage for New York city's bike sharing system Aaai Workshop - Technical Report. 110-114.  0.095
1996 Loui MC, Condon A, Fich F, Frederickson GN, Goldberg AV, Johnson DS, Mahaney S, Raghavan P, Savage J, Selman AL, Shmoys DB. Strategic directions in research in theory of computing Acm Computing Surveys. 28. DOI: 10.1145/262301.262310  0.094
1984 West DB, Shmoys DB. Recognizing graphs with fixed interval number is NP-complete Discrete Applied Mathematics. 8: 295-305. DOI: 10.1016/0166-218X(84)90127-6  0.091
2000 Vision TJ, Brown DG, Shmoys DB, Durrett RT, Tanksley SD. Selective mapping: a strategy for optimizing the construction of high-density linkage maps. Genetics. 155: 407-20. PMID 10790413  0.086
1995 Shmoys DB, Wein J, Williamson DP. Scheduling Parallel Machines On-Line Siam Journal On Computing. 24: 1313-1331. DOI: 10.1137/S0097539793248317  0.083
2019 Gomes C, Dietterich T, Barrett C, Conrad J, Dilkina B, Ermon S, Fang F, Farnsworth A, Fern A, Fern X, Fink D, Fisher D, Flecker A, Freund D, Fuller A, ... ... Shmoys D, et al. Computational sustainability Communications of the Acm. 62: 56-65. DOI: 10.1145/3339399  0.064
2023 Wan J, Cazer CL, Clarkberg ME, Henderson SG, Lee SE, Meredith GR, Osman M, Shmoys DB, Frazier PI. Booster vaccination protection against SARS-CoV-2 infections in young adults during an Omicron BA.1-predominant period: A retrospective cohort study. Plos Medicine. 20: e1004153. PMID 36626376 DOI: 10.1371/journal.pmed.1004153  0.017
Hide low-probability matches.