☰

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
Tree Info Similar researchers PubMed Report error

65 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
Show low-probability matches.