dblp.uni-trier.dewww.uni-trier.de

David B. Shmoys

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo
Home Page

2008
68EETim Carnes, David B. Shmoys: Primal-Dual Schema for Capacitated Covering Problems. IPCO 2008: 288-302
67EEDavid B. Shmoys, Kunal Talwar: A Constant Approximation Algorithm for the a prioriTraveling Salesman Problem. IPCO 2008: 331-343
66EEChaitanya Swamy, David B. Shmoys: Fault-tolerant facility location. ACM Transactions on Algorithms 4(4): (2008)
65EEFrans Schalekamp, David B. Shmoys: Algorithms for the universal and a priori TSP. Oper. Res. Lett. 36(1): 1-3 (2008)
2007
64EEDavid B. Shmoys, Mauro Sozio: Approximation Algorithms for 2-Stage Stochastic Scheduling Problems. IPCO 2007: 145-157
63EEChaitanya Swamy, David B. Shmoys: Sampling-based Approximation Algorithms for Multi-stage Stochastic Optimization. Probabilistic Methods in the Design and Analysis of Algorithms 2007
2006
62EEChaitanya Swamy, David B. Shmoys: Approximation Algorithms for 2-Stage Stochastic Optimization Problems. FSTTCS 2006: 5-19
61EERetsef Levi, Robin Roundy, David B. Shmoys: Provably near-optimal sampling-based algorithms for Stochastic inventory control models. STOC 2006: 739-748
60EEDavid 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)
59EEChaitanya Swamy, David B. Shmoys: Approximation algorithms for 2-stage stochastic optimization problems. SIGACT News 37(1): 33-46 (2006)
2005
58EEChaitanya Swamy, David B. Shmoys: Approximation Algorithms for 2-stage and Multi-stage Stochastic Optimization. Algorithms for Optimization with Incomplete Information 2005
57EEChaitanya Swamy, David B. Shmoys: Sampling-based Approximation Algorithms for Multi-stage Stochastic. FOCS 2005: 357-366
56EERetsef Levi, Joseph Geunes, H. Edwin Romeijn, David B. Shmoys: Inventory and Facility Location Models with Market Selection. IPCO 2005: 111-124
55EERetsef Levi, Martin Pál, Robin Roundy, David B. Shmoys: Approximation Algorithms for Stochastic Inventory Control Models. IPCO 2005: 306-320
54EERetsef Levi, Robin Roundy, David B. Shmoys: A constant approximation algorithm for the one-warehouse multi-retailer problem. SODA 2005: 365-374
2004
53EEDavid B. Shmoys, Chaitanya Swamy: Stochastic Optimization is (Almost) as easy as Deterministic Optimization. FOCS 2004: 228-237
52EERetsef Levi, David B. Shmoys, Chaitanya Swamy: LP-based Approximation Algorithms for Capacitated Facility Location. IPCO 2004: 206-218
51EEDavid B. Shmoys, Chaitanya Swamy, Retsef Levi: Facility location with Service Installation Costs. SODA 2004: 1088-1097
50EERetsef Levi, Robin Roundy, David B. Shmoys: Primal-dual algorithms for deterministic inventory problems. STOC 2004: 353-362
49EECarla P. Gomes, David B. Shmoys: Approximations and Randomization to Boost CSP Techniques. Annals OR 130(1-4): 117-141 (2004)
48EEDavid B. Shmoys: Foreword. J. Algorithms 50(2): 133 (2004)
47EECarla 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)
2003
46EEAaron Archer, Ranjithkumar Rajagopalan, David B. Shmoys: Lagrangian Relaxation for the k-Median Problem: New Insights and Continuity Properties. ESA 2003: 31-42
45EEChaitanya Swamy, David B. Shmoys: Fault-tolerant facility location. SODA 2003: 735-736
44EECarla P. Gomes, Rommel G. Regis, David B. Shmoys: An improved approximation algorithm for the partial latin square extension problem. SODA 2003: 832-833
43EEFabián A. Chudak, David B. Shmoys: Improved Approximation Algorithms for the Uncapacitated Facility Location Problem. SIAM J. Comput. 33(1): 1-25 (2003)
2002
42EEMoses 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)
2000
41EEDavid B. Shmoys: Approximation algorithms for facility location problems. APPROX 2000: 27-33
1999
40EEDavid B. Shmoys: Approximation Algorithms for Clustering Problems. COLT 1999: 100-102
39EEFabián A. Chudak, David B. Shmoys: Improved Approximation Algorithms for a Capacitated Facility Location Problem. SODA 1999: 875-876
38EEMoses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys: A Constant-Factor Approximation Algorithm for the k-Median Problem (Extended Abstract). STOC 1999: 1-10
37EEKaren 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)
36 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)
1998
35EEDavid B. Shmoys: Using Linear Programming in the Design and Analysis of Approximation Algorithms: Two Illustrative Problems. APPROX 1998: 15-32
34 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)
1997
33 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
32EEDavid B. Shmoys, Éva Tardos, Karen Aardal: Approximation Algorithms for Facility Location Problems (Extended Abstract). STOC 1997: 265-274
1996
31 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
30 Paul Martin, David B. Shmoys: A New Approach to Computing Optimal Schedules for the Job-Shop Scheduling Problem. IPCO 1996: 389-403
29 Leslie A. Hall, David B. Shmoys, Joel Wein: Scheduling to Minimize Average Completion Time: Off-line and On-line Algorithms. SODA 1996: 142-151
1995
28 David B. Shmoys, Joel Wein, David P. Williamson: Scheduling Parallel Machines On-Line. SIAM J. Comput. 24(6): 1313-1331 (1995)
1994
27 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
26 David B. Shmoys, Clifford Stein, Joel Wein: Improved Approximation Algorithms for Shop Scheduling Problems. SIAM J. Comput. 23(3): 617-632 (1994)
1993
25 David B. Shmoys, Éva Tardos: Scheduling Unrelated Machines with Costs. SODA 1993: 448-454
24 David B. Shmoys, Éva Tardos: An approximation algorithm for the generalized assignment problem. Math. Program. 62: 461-474 (1993)
1992
23 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)
1991
22 David B. Shmoys, Joel Wein, David P. Williamson: Scheduling Parallel Machines On-Line FOCS 1991: 131-140
21 Serge A. Plotkin, David B. Shmoys, Éva Tardos: Fast Approximation Algorithms for Fractional Packing and Covering Problems FOCS 1991: 495-504
20 David B. Shmoys, Clifford Stein, Joel Wein: Improved Approximation Algorithms for Shop Scheduling Problems. SODA 1991: 148-157
1990
19 Leslie A. Hall, David B. Shmoys: Near-Optimal Sequencing with Precedence Constraints. IPCO 1990: 249-260
18 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)
17 Jan Karel Lenstra, David B. Shmoys, Éva Tardos: Approximation Algorithms for Scheduling Unrelated Parallel Machines. Math. Program. 46: 259-271 (1990)
16 Cynthia Dwork, David B. Shmoys, Larry J. Stockmeyer: Flipping Persuasively in Constant Time. SIAM J. Comput. 19(3): 472-499 (1990)
1989
15 Leslie A. Hall, David B. Shmoys: Approximation Schemes for Constrained Scheduling Problems FOCS 1989: 134-139
14 Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos: Interior-Point Methods in Parallel Computation FOCS 1989: 350-355
13EEBenny Chor, Michael Merritt, David B. Shmoys: Simple constant-time consensus protocols in realistic failure models. J. ACM 36(3): 591-614 (1989)
12 Gerard A. P. Kindervater, Jan Karel Lenstra, David B. Shmoys: The Parallel Complexity of TSP Heuristics. J. Algorithms 10(2): 249-270 (1989)
1988
11 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)
1987
10 Jan Karel Lenstra, David B. Shmoys, Éva Tardos: Approximation Algorithms for Scheduling Unrelated Parallel Machines FOCS 1987: 217-224
9EEDorit S. Hochbaum, David B. Shmoys: Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM 34(1): 144-162 (1987)
8 Howard J. Karloff, David B. Shmoys: Efficient Parallel Algorithms for Edge Coloring Problems. J. Algorithms 8(1): 39-52 (1987)
1986
7 Cynthia Dwork, David B. Shmoys, Larry J. Stockmeyer: Flipping Persuasively in Constant Expected Time (Preliminary Version) FOCS 1986: 222-232
6 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
5EEDorit S. Hochbaum, David B. Shmoys: A unified approach to approximation algorithms for bottleneck problems. J. ACM 33(3): 533-550 (1986)
4 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)
1985
3 Dorit S. Hochbaum, David B. Shmoys: Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results FOCS 1985: 79-89
2 Benny Chor, Michael Merritt, David B. Shmoys: Simple Constant-Time Consensus Protocols in Realistic Failure Models (Extended Abstract). PODC 1985: 152-162
1984
1 Dorit S. Hochbaum, David B. Shmoys: Powers of Graphs: A Powerful Approximation Technique for Bottleneck Problems STOC 1984: 324-333

Coauthor Index

1Karen Aardal [32] [37]
2Aaron Archer [46]
3Tim Carnes [68]
4Soumen Chakrabarti [31]
5Moses Charikar [38] [42]
6Benny Chor [2] [13]
7Fabián A. Chudak [33] [36] [37] [39] [43]
8Cynthia Dwork [7] [16]
9Joseph Geunes [56]
10Michel X. Goemans [27]
11Andrew V. Goldberg [14] [23] [27]
12Carla P. Gomes [44] [47] [49]
13Sudipto Guha [38] [42]
14Leslie A. Hall [15] [19] [29]
15Dorit S. Hochbaum [1] [3] [4] [5] [6] [9] [11]
16Howard J. Karloff [8]
17Gerard A. P. Kindervater [12]
18Jan Karel Lenstra [10] [12] [17]
19Retsef Levi [50] [51] [52] [54] [55] [56] [61]
20Paul Martin [30]
21Michael Merritt [2] [13]
22Takao Nishizeki [4]
23Martin Pál (Martin Pal) [55]
24Cynthia A. Phillips [31] [34]
25Serge A. Plotkin [14] [21] [23] [27]
26Ranjithkumar Rajagopalan [46]
27Rommel G. Regis [44] [47]
28H. Edwin Romeijn [56]
29Robin Roundy [50] [54] [55] [61]
30Frans Schalekamp [65]
31Andreas S. Schulz [31] [34]
32Mauro Sozio [64]
33Clifford Stein [20] [26] [31] [34]
34Larry J. Stockmeyer [7] [16]
35Chaitanya Swamy [45] [51] [52] [53] [57] [58] [59] [60] [62] [63] [66]
36Kunal Talwar [67]
37Éva Tardos [10] [14] [17] [21] [23] [24] [25] [27] [32] [38] [42]
38Joel Wein [20] [22] [26] [28] [29] [31] [34]
39David P. Williamson [18] [22] [27] [28]

Colors in the list of coauthors

Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)