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 |