David B. Shmoys

2008
68	EE	Tim Carnes, David B. Shmoys: Primal-Dual Schema for Capacitated Covering Problems. IPCO 2008: 288-302
67	EE	David B. Shmoys, Kunal Talwar: A Constant Approximation Algorithm for the a prioriTraveling Salesman Problem. IPCO 2008: 331-343
66	EE	Chaitanya Swamy, David B. Shmoys: Fault-tolerant facility location. ACM Transactions on Algorithms 4(4): (2008)
65	EE	Frans Schalekamp, David B. Shmoys: Algorithms for the universal and a priori TSP. Oper. Res. Lett. 36(1): 1-3 (2008)
2007
64	EE	David B. Shmoys, Mauro Sozio: Approximation Algorithms for 2-Stage Stochastic Scheduling Problems. IPCO 2007: 145-157
63	EE	Chaitanya Swamy, David B. Shmoys: Sampling-based Approximation Algorithms for Multi-stage Stochastic Optimization. Probabilistic Methods in the Design and Analysis of Algorithms 2007
2006
62	EE	Chaitanya Swamy, David B. Shmoys: Approximation Algorithms for 2-Stage Stochastic Optimization Problems. FSTTCS 2006: 5-19
61	EE	Retsef Levi, Robin Roundy, David B. Shmoys: Provably near-optimal sampling-based algorithms for Stochastic inventory control models. STOC 2006: 739-748
60	EE	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)
59	EE	Chaitanya Swamy, David B. Shmoys: Approximation algorithms for 2-stage stochastic optimization problems. SIGACT News 37(1): 33-46 (2006)
2005
58	EE	Chaitanya Swamy, David B. Shmoys: Approximation Algorithms for 2-stage and Multi-stage Stochastic Optimization. Algorithms for Optimization with Incomplete Information 2005
57	EE	Chaitanya Swamy, David B. Shmoys: Sampling-based Approximation Algorithms for Multi-stage Stochastic. FOCS 2005: 357-366
56	EE	Retsef Levi, Joseph Geunes, H. Edwin Romeijn, David B. Shmoys: Inventory and Facility Location Models with Market Selection. IPCO 2005: 111-124
55	EE	Retsef Levi, Martin Pál, Robin Roundy, David B. Shmoys: Approximation Algorithms for Stochastic Inventory Control Models. IPCO 2005: 306-320
54	EE	Retsef Levi, Robin Roundy, David B. Shmoys: A constant approximation algorithm for the one-warehouse multi-retailer problem. SODA 2005: 365-374
2004
53	EE	David B. Shmoys, Chaitanya Swamy: Stochastic Optimization is (Almost) as easy as Deterministic Optimization. FOCS 2004: 228-237
52	EE	Retsef Levi, David B. Shmoys, Chaitanya Swamy: LP-based Approximation Algorithms for Capacitated Facility Location. IPCO 2004: 206-218
51	EE	David B. Shmoys, Chaitanya Swamy, Retsef Levi: Facility location with Service Installation Costs. SODA 2004: 1088-1097
50	EE	Retsef Levi, Robin Roundy, David B. Shmoys: Primal-dual algorithms for deterministic inventory problems. STOC 2004: 353-362
49	EE	Carla P. Gomes, David B. Shmoys: Approximations and Randomization to Boost CSP Techniques. Annals OR 130(1-4): 117-141 (2004)
48	EE	David B. Shmoys: Foreword. J. Algorithms 50(2): 133 (2004)
47	EE	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)
2003
46	EE	Aaron Archer, Ranjithkumar Rajagopalan, David B. Shmoys: Lagrangian Relaxation for the k-Median Problem: New Insights and Continuity Properties. ESA 2003: 31-42
45	EE	Chaitanya Swamy, David B. Shmoys: Fault-tolerant facility location. SODA 2003: 735-736
44	EE	Carla P. Gomes, Rommel G. Regis, David B. Shmoys: An improved approximation algorithm for the partial latin square extension problem. SODA 2003: 832-833
43	EE	Fabián A. Chudak, David B. Shmoys: Improved Approximation Algorithms for the Uncapacitated Facility Location Problem. SIAM J. Comput. 33(1): 1-25 (2003)
2002
42	EE	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)
2000
41	EE	David B. Shmoys: Approximation algorithms for facility location problems. APPROX 2000: 27-33
1999
40	EE	David B. Shmoys: Approximation Algorithms for Clustering Problems. COLT 1999: 100-102
39	EE	Fabián A. Chudak, David B. Shmoys: Improved Approximation Algorithms for a Capacitated Facility Location Problem. SODA 1999: 875-876
38	EE	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
37	EE	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)
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
35	EE	David 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
32	EE	David 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
13	EE	Benny 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
9	EE	Dorit 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
5	EE	Dorit 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

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

Colors in the list of coauthors