×

zbMATH — the first resource for mathematics

Shmoys, David B.

Compute Distance To:
Author ID: shmoys.david-b Recent zbMATH articles by "Shmoys, David B."
Published as: Shmoys, David B.; Shmoys, David; Shmoys, D. B.
External Links: MGP · Wikidata · GND
Documents Indexed: 101 Publications since 1984, including 2 Books
all top 5

Co-Authors

4 single-authored
15 Levi, Retsef
11 Tardos, Éva
10 Williamson, David P.
9 Roundy, Robin O.
8 Hochbaum, Dorit S.
8 Swamy, Chaitanya
8 Wein, Joel M.
7 Lenstra, Jan Karel
5 Chudak, Fabián A.
4 Hall, Leslie A.
4 Kleinberg, Robert D.
4 Schulz, Andreas S.
4 Stein, Clifford
3 An, Hyung-Chan
3 Carnes, Tim
3 Cheung, Maurice
3 Freund, Daniel
3 Gomes, Carla P.
3 Lawler, Eugene L.
3 Plotkin, Serge A.
3 Spencer, Gwen
2 Aardal, Karen I.
2 Charikar, Moses S.
2 Ferber, Aaron
2 Geunes, Joseph
2 Goldberg, Andrew V.
2 Guha, Sudipto
2 Henderson, Shane G.
2 Pál, Martin
2 Paul, Alice
2 Phillips, Cynthia A.
2 Regis, Rommel G.
2 Rinnooy Kan, Alexander Hendrik George
2 Romeijn, H. Edwin
2 Rusmevichientong, Paat
2 Shen, Zuo-Jun Max
1 Alamdari, Soroush
1 Archer, Aaron F.
1 Awerbuch, Baruch
1 Batterson, Steve
1 Ben-Or, Michael
1 Burkard, Rainer E.
1 Chakrabarti, Soumen
1 Chandra, Ashok K.
1 Chor, Benny
1 Dwork, Cynthia
1 Elmachtoub, Adam N.
1 Feigenbaum, Joan
1 Gilmore, Paul C.
1 Goemans, Michel X.
1 Gorodezky, Igor
1 Guibas, Leonidas John
1 Halpern, Joseph Yehuda
1 Hoogeveen, Johannes Adzer
1 Hurkens, Cor A. J.
1 Karloff, Howard J.
1 Kindervater, Gerard A. P.
1 Lovász, László
1 Merritt, Michael J.
1 Mestre, Julián
1 Nishizeki, Takao
1 Pitt, Leonard
1 Potts, Chris N.
1 Rajagopalan, Ranjithkumar
1 Saks, Michael E.
1 Schalekamp, Frans
1 Sevastyanov, Sergeĭ Vasil’evich
1 Sozio, Mauro
1 Steele, Patrick R.
1 Stockmeyer, Larry J.
1 Sviridenko, Maxim I.
1 Talwar, Kunal
1 Truong, Van Anh
1 Upfal, Eli
1 Vazirani, Umesh V.
1 Verschae, José
1 von zur Gathen, Joachim
1 West, Douglas Brent
1 Yao, Andrew Chi-Chih
1 Zimmermann, Uwe T.

Publications by Year

Citations contained in zbMATH Open

85 Publications have been cited 2,348 times in 1,820 Documents Cited by Year
The traveling salesman problem. A guided tour of combinatorial optimization. Reprint. Zbl 0562.00014
Lawler, E. L. (ed.); Lenstra, J. K. (ed.); Rinnooy Kan, A. H. G. (ed.); Shmoys, D. B. (ed.)
181
1985
Approximation algorithms for scheduling unrelated parallel machines. Zbl 0715.90063
Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva
175
1990
The traveling salesman problem. Bibliography. Zbl 0563.90075
Lawler, E. L. (ed.); Lenstra, J. K. (ed.); Rinnooy Kan, A. H. G. (ed.); Shmoys, D. B. (ed.)
147
1985
The design of approximation algorithms. Zbl 1219.90004
Williamson, David P.; Shmoys, David B.
131
2011
Approximation algorithms for facility location problems. (Extended abstract). Zbl 0962.68008
Shmoys, David B.; Tardos, Éva; Aardal, Karen
128
1999
A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract). Zbl 1346.68253
Charikar, Moses; Guha, Sudipto; Tardos, Éva; Shmoys, David B.
113
1999
Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Zbl 0883.90064
Hall, Leslie A.; Schulz, Andreas S.; Shmoys, David B.; Wein, Joel
100
1997
A best possible heuristic for the k-center problem. Zbl 0565.90015
Hochbaum, Dorit S.; Shmoys, David B.
92
1985
An approximation algorithm for the generalized assignment problem. Zbl 0804.90077
Shmoys, David B.; Tardos, Éva
92
1993
A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach. Zbl 0647.68040
Hochbaum, Dorit S.; Shmoys, David B.
68
1988
Improved approximation algorithms for the uncapacitated facility location problem. Zbl 1044.90056
Chudak, Fabián A.; Shmoys, David B.
66
2003
Well-solved special cases. Zbl 0631.90081
Gilmore, P. C.; Lawler, E. L.; Shmoys, D. B.
65
1985
Fast approximation algorithms for fractional packing and covering problems. Zbl 0837.90103
Plotkin, Serge A.; Shmoys, David B.; Tardos, Éva
62
1995
Short shop schedules. Zbl 0890.90112
Williamson, D. P.; Hall, L. A.; Hoogeveen, J. A.; Hurkens, C. A. J.; Lenstra, J. K.; Sevast’janov, S. V.; Shmoys, D. B.
56
1997
Improved approximation algorithms for network design problems. Zbl 0873.68005
Goemans, M. X.; Goldberg, A. V.; Plotkin, S.; Shmoys, D. B.; Tardos, É.; Williamson, D. P.
50
1994
Jackson’s rule for single-machine scheduling: Making a good heuristic better. Zbl 0781.90052
Hall, Leslie A.; Shmoys, David B.
43
1992
Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Zbl 1228.90170
Rusmevichientong, Paat; Shen, Zuo-Jun Max; Shmoys, David B.
42
2010
A constant-factor approximation algorithm for the \(k\)-median problem. Zbl 1023.90037
Charikar, Moses; Guha, Sudipto; Tardos, Éva; Shmoys, David B.
41
2002
Scheduling parallel machines on-line. Zbl 0845.68042
Shmoys, David B.; Wein, Joel; Williamson, David P.
40
1995
A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem. Zbl 0994.90090
Aardal, Karen; Chudak, Fabián A.; Shmoys, David B.
37
1999
Improved approximation algorithms for shop scheduling problems. Zbl 0814.68026
Shmoys, David B.; Stein, Clifford; Wein, Joel
35
1994
Provably near-optimal sampling-based policies for stochastic inventory control models. Zbl 1341.90005
Levi, Retsef; Roundy, Robin O.; Shmoys, David B.
30
2007
A constant approximation algorithm for the one-warehouse multiretailer problem. Zbl 1232.90071
Levi, Retsef; Roundy, Robin; Shmoys, David; Sviridenko, Maxim
30
2008
Analyzing the Held-Karp TSP bound: A monotonicity property with application. Zbl 0698.68050
Shmoys, David B.; Williamson, David P.
28
1990
Scheduling to minimize average completion time: Off-line and on-line algorithms. Zbl 0845.90071
Hall, Leslie A.; Shmoys, David B.; Wein, Joel
26
1996
Improved scheduling algorithms for minsum criteria (extended abstract). Zbl 1046.68505
Chakrabarti, Soumen; Phillips, Cynthia A.; Schulz, Andreas S.; Shmoys, David B.; Stein, Cliff; Wein, Joel
25
1996
Permutation vs. non-permutation flow shop schedules. Zbl 0742.90045
Potts, Chris N.; Shmoys, David B.; Williamson, David P.
23
1991
Recognizing graphs with fixed interval number is NP-complete. Zbl 0554.68041
West, Douglas B.; Shmoys, David B.
22
1984
Primal-dual algorithms for deterministic inventory problems. Zbl 1278.90026
Levi, Retsef; Roundy, Robin O.; Shmoys, David B.
18
2006
Improved approximation algorithms for a capacitated facility location problem. Zbl 1052.90580
Chudak, Fabián A.; Shmoys, David B.
18
1999
Approximation algorithms for facility location problems. Zbl 0976.68538
Shmoys, David B.
18
2000
Primal-dual schema for capacitated covering problems. Zbl 1143.90375
Carnes, Tim; Shmoys, David
17
2008
Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. Zbl 0923.68012
Chudak, Fabián A.; Shmoys, David B.
17
1999
An approximation scheme for stochastic linear programming and its application to stochastic integer programs. Zbl 1326.90059
Shmoys, David B.; Swamy, Chaitanya
15
2006
Improving Christofides’ algorithm for the \(s\)-\(t\) path TSP. Zbl 1286.68173
An, Hyung-Chan; Kleinberg, Robert; Shmoys, David B.
13
2012
A new approach to computing optimal schedules for the job-shop scheduling problem. Zbl 1414.90162
Martin, Paul; Shmoys, David B.
12
1996
Approximation algorithms for supply chain planning and logistics problems with market choice. Zbl 1229.90011
Geunes, Joseph; Levi, Retsef; Romeijn, H. Edwin; Shmoys, David B.
12
2011
Approximation algorithms for capacitated stochastic inventory control models. Zbl 1167.90339
Levi, Retsef; Roundy, Robin O.; Shmoys, David B.; Truong, Van Anh
11
2008
A constant approximation algorithm for the a priori traveling salesman problem. Zbl 1143.90383
Shmoys, David; Talwar, Kunal
10
2008
A better than ”best possible” algorithm to edge color multigraphs. Zbl 0594.68041
Hochbaum, Dorit S.; Nishizeki, Takao; Shmoys, David B.
10
1986
Efficient parallel algorithms for edge coloring problems. Zbl 0642.68125
Karloff, Howard J.; Shmoys, David B.
10
1987
Scheduling unrelated machines with costs. Zbl 0801.68014
Shmoys, David B.; Tardos, Éva
10
1993
Approximation algorithms for 2-stage stochastic optimization problems. Zbl 1177.90302
Swamy, Chaitanya; Shmoys, David B.
9
2006
Approximation algorithms for stochastic inventory control models. Zbl 1279.90011
Levi, Retsef; Pál, Martin; Roundy, Robin O.; Shmoys, David B.
9
2007
Improved approximation algorithms for shop scheduling problems. Zbl 0800.68222
Shmoys, David B.; Stein, Clifford; Wein, Joel
9
1991
A PTAS for capacitated sum-of-ratios optimization. Zbl 1167.90493
Rusmevichientong, Paat; Shen, Zuo-Jun Max; Shmoys, David B.
8
2009
Fault-tolerant facility location. Zbl 1445.68356
Swamy, Chaitanya; Shmoys, David B.
8
2008
Improving Christofides’ algorithm for the \(s\)-\(t\) path TSP. Zbl 1426.68300
An, Hyung-Chan; Kleinberg, Robert; Shmoys, David B.
8
2015
Fault-tolerant facility location. Zbl 1092.68737
Swamy, Chaitanya; Shmoys, David B.
8
2003
LP-based approximation algorithms for capacitated facility location. Zbl 1092.90524
Levi, Retsef; Shmoys, David B.; Swamy, Chaitanya
8
2004
LP-based approximation algorithms for capacitated facility location. Zbl 1247.90055
Levi, Retsef; Shmoys, David B.; Swamy, Chaitanya
8
2012
Facility location with service installation costs. Zbl 1318.90044
Shmoys, David B.; Swamy, Chaitanya; Levi, Retsef
7
2004
Flipping persuasively in constant time. Zbl 0698.68043
Dwork, Cynthia; Shmoys, David; Stockmeyer, Larry
7
1990
Scheduling parallel machines on-line. Zbl 0800.68214
Shmoys, David B.; Wein, Joel; Williamson, David P.
7
1992
Algorithms for the universal and a priori TSP. Zbl 1151.90040
Schalekamp, Frans; Shmoys, David B.
7
2008
Improved lower bounds for the universal and a priori TSP. Zbl 1304.68062
Gorodezky, Igor; Kleinberg, Robert D.; Shmoys, David B.; Spencer, Gwen
7
2010
Lagrangian relaxation for the \(k\)-median problem: new insights and continuity properties. Zbl 1266.90117
Archer, Aaron; Rajagopalan, Ranjithkumar; Shmoys, David B.
7
2003
A primal-dual approximation algorithm for Min-sum single-machine scheduling problems. Zbl 1365.90226
Cheung, Maurice; Mestre, Julián; Shmoys, David B.; Verschae, José
6
2017
A primal-dual approximation algorithm for min-sum single-machine scheduling problems. Zbl 1343.68310
Cheung, Maurice; Shmoys, David B.
6
2011
Sampling-based approximation algorithms for multistage stochastic optimization. Zbl 1253.68379
Swamy, Chaitanya; Shmoys, David B.
6
2012
Primal-dual schema for capacitated covering problems. Zbl 1327.90252
Carnes, Tim; Shmoys, David B.
5
2015
Inventory and facility location models with market selection. Zbl 1119.90323
Levi, Retsef; Geunes, Joseph; Romeijn, H. Edwin; Shmoys, David B.
5
2005
Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. Zbl 1321.68497
Chudak, Fabián A.; Shmoys, David B.
4
1997
A constant approximation algorithm for the one-warehouse multi-retailer problem. Zbl 1297.90004
Levi, Retsef; Roundy, Robin; Shmoys, David B.
4
2005
The submodular joint replenishment problem. Zbl 1346.90301
Cheung, Maurice; Elmachtoub, Adam N.; Levi, Retsef; Shmoys, David B.
4
2016
Approximation algorithms for 2-stage stochastic scheduling problems. Zbl 1136.90358
Shmoys, David B.; Sozio, Mauro
4
2007
An \(O(| V| ^ 2)\) algorithm for the planar 3-cut problem. Zbl 0572.05040
Hochbaum, Dorit S.; Shmoys, David B.
4
1985
Simple constant-time consensus protocols in realistic failure models. Zbl 0675.90038
Chor, Benny; Merritt, Michael; Shmoys, David B.
4
1989
Using linear programming in the design and analysis of approximation algorithms: Two illustrative problems. Zbl 0907.90186
Shmoys, David B.
4
1998
Minimizing multimodular functions and allocating capacity in bike-sharing systems. Zbl 1418.90164
Freund, Daniel; Henderson, Shane G.; Shmoys, David B.
3
2017
Improved bounds on relaxations of a parallel machine scheduling problem. Zbl 0911.90219
Phillips, Cynthia A.; Schulz, Andreas S.; Shmoys, David B.; Stein, Cliff; Wein, Joel
3
1998
Computing near-optimal solutions to combinatorial optimization problems. Zbl 0835.90081
Shmoys, David B.
3
1995
The design and analysis of approximation algorithms: facility location as a case study. Zbl 1130.90043
Shmoys, David B.
3
2004
Approximation algorithms for stochastic inventory control models. Zbl 1119.90300
Levi, Retsef; Pál, Martin; Roundy, Robin; Shmoys, David B.
3
2005
The parallel complexity of TSP heuristics. Zbl 0679.68086
Kindervater, Gerard A. P.; Lenstra, Jan Karel; Shmoys, David B.
3
1989
Approximations and randomization to boost CSP techniques. Zbl 1062.90033
Gomes, Carla P.; Shmoys, David B.
3
2004
Primal-dual schema and Lagrangian relaxation for the \(k\)-location-routing problem. Zbl 1343.68309
Carnes, Tim; Shmoys, David B.
3
2011
Using interior-point methods for fast parallel algorithms for bipartite matching and related problems. Zbl 0743.68074
Goldberg, Andrew V.; Plotkin, Serge A.; Shmoys, David B.; Tardos, Eva
2
1992
An improved approximation algorithm for the partial latin square extension problem. Zbl 1141.68659
Gomes, Carla P.; Regis, Rommel G.; Shmoys, David B.
2
2003
Best possible heuristics for the bottleneck wandering salesperson and bottleneck vehicle routing problem. Zbl 0596.90093
Hochbaum, Dorit S.; Shmoys, David B.
2
1986
Provably near-optimal sampling-based algorithms for stochastic inventory control models. Zbl 1301.68274
Levi, Retsef; Roundy, Robin O.; Shmoys, David B.
2
2006
Computational complexity. Zbl 0844.68046
Shmoys, D. B.; Tardos, É.
1
1995
A bicriteria approximation algorithm for the \(k\)-center and \(k\)-median problems. Zbl 1442.68261
Alamdari, Soroush; Shmoys, David
1
2018
A polynomial approximation scheme for machine scheduling on uniform processors: Using the dual approximation approach. Zbl 0623.68033
Hochbaum, Dorit S.; Shmoys, David B.
1
1986
An improved approximation algorithm for the partial Latin square extension problem. Zbl 1078.68160
Gomes, Carla P.; Regis, Rommel G.; Shmoys, David B.
1
2004
A bicriteria approximation algorithm for the \(k\)-center and \(k\)-median problems. Zbl 1442.68261
Alamdari, Soroush; Shmoys, David
1
2018
A primal-dual approximation algorithm for Min-sum single-machine scheduling problems. Zbl 1365.90226
Cheung, Maurice; Mestre, Julián; Shmoys, David B.; Verschae, José
6
2017
Minimizing multimodular functions and allocating capacity in bike-sharing systems. Zbl 1418.90164
Freund, Daniel; Henderson, Shane G.; Shmoys, David B.
3
2017
The submodular joint replenishment problem. Zbl 1346.90301
Cheung, Maurice; Elmachtoub, Adam N.; Levi, Retsef; Shmoys, David B.
4
2016
Improving Christofides’ algorithm for the \(s\)-\(t\) path TSP. Zbl 1426.68300
An, Hyung-Chan; Kleinberg, Robert; Shmoys, David B.
8
2015
Primal-dual schema for capacitated covering problems. Zbl 1327.90252
Carnes, Tim; Shmoys, David B.
5
2015
Improving Christofides’ algorithm for the \(s\)-\(t\) path TSP. Zbl 1286.68173
An, Hyung-Chan; Kleinberg, Robert; Shmoys, David B.
13
2012
LP-based approximation algorithms for capacitated facility location. Zbl 1247.90055
Levi, Retsef; Shmoys, David B.; Swamy, Chaitanya
8
2012
Sampling-based approximation algorithms for multistage stochastic optimization. Zbl 1253.68379
Swamy, Chaitanya; Shmoys, David B.
6
2012
The design of approximation algorithms. Zbl 1219.90004
Williamson, David P.; Shmoys, David B.
131
2011
Approximation algorithms for supply chain planning and logistics problems with market choice. Zbl 1229.90011
Geunes, Joseph; Levi, Retsef; Romeijn, H. Edwin; Shmoys, David B.
12
2011
A primal-dual approximation algorithm for min-sum single-machine scheduling problems. Zbl 1343.68310
Cheung, Maurice; Shmoys, David B.
6
2011
Primal-dual schema and Lagrangian relaxation for the \(k\)-location-routing problem. Zbl 1343.68309
Carnes, Tim; Shmoys, David B.
3
2011
Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Zbl 1228.90170
Rusmevichientong, Paat; Shen, Zuo-Jun Max; Shmoys, David B.
42
2010
Improved lower bounds for the universal and a priori TSP. Zbl 1304.68062
Gorodezky, Igor; Kleinberg, Robert D.; Shmoys, David B.; Spencer, Gwen
7
2010
A PTAS for capacitated sum-of-ratios optimization. Zbl 1167.90493
Rusmevichientong, Paat; Shen, Zuo-Jun Max; Shmoys, David B.
8
2009
A constant approximation algorithm for the one-warehouse multiretailer problem. Zbl 1232.90071
Levi, Retsef; Roundy, Robin; Shmoys, David; Sviridenko, Maxim
30
2008
Primal-dual schema for capacitated covering problems. Zbl 1143.90375
Carnes, Tim; Shmoys, David
17
2008
Approximation algorithms for capacitated stochastic inventory control models. Zbl 1167.90339
Levi, Retsef; Roundy, Robin O.; Shmoys, David B.; Truong, Van Anh
11
2008
A constant approximation algorithm for the a priori traveling salesman problem. Zbl 1143.90383
Shmoys, David; Talwar, Kunal
10
2008
Fault-tolerant facility location. Zbl 1445.68356
Swamy, Chaitanya; Shmoys, David B.
8
2008
Algorithms for the universal and a priori TSP. Zbl 1151.90040
Schalekamp, Frans; Shmoys, David B.
7
2008
Provably near-optimal sampling-based policies for stochastic inventory control models. Zbl 1341.90005
Levi, Retsef; Roundy, Robin O.; Shmoys, David B.
30
2007
Approximation algorithms for stochastic inventory control models. Zbl 1279.90011
Levi, Retsef; Pál, Martin; Roundy, Robin O.; Shmoys, David B.
9
2007
Approximation algorithms for 2-stage stochastic scheduling problems. Zbl 1136.90358
Shmoys, David B.; Sozio, Mauro
4
2007
Primal-dual algorithms for deterministic inventory problems. Zbl 1278.90026
Levi, Retsef; Roundy, Robin O.; Shmoys, David B.
18
2006
An approximation scheme for stochastic linear programming and its application to stochastic integer programs. Zbl 1326.90059
Shmoys, David B.; Swamy, Chaitanya
15
2006
Approximation algorithms for 2-stage stochastic optimization problems. Zbl 1177.90302
Swamy, Chaitanya; Shmoys, David B.
9
2006
Provably near-optimal sampling-based algorithms for stochastic inventory control models. Zbl 1301.68274
Levi, Retsef; Roundy, Robin O.; Shmoys, David B.
2
2006
Inventory and facility location models with market selection. Zbl 1119.90323
Levi, Retsef; Geunes, Joseph; Romeijn, H. Edwin; Shmoys, David B.
5
2005
A constant approximation algorithm for the one-warehouse multi-retailer problem. Zbl 1297.90004
Levi, Retsef; Roundy, Robin; Shmoys, David B.
4
2005
Approximation algorithms for stochastic inventory control models. Zbl 1119.90300
Levi, Retsef; Pál, Martin; Roundy, Robin; Shmoys, David B.
3
2005
LP-based approximation algorithms for capacitated facility location. Zbl 1092.90524
Levi, Retsef; Shmoys, David B.; Swamy, Chaitanya
8
2004
Facility location with service installation costs. Zbl 1318.90044
Shmoys, David B.; Swamy, Chaitanya; Levi, Retsef
7
2004
The design and analysis of approximation algorithms: facility location as a case study. Zbl 1130.90043
Shmoys, David B.
3
2004
Approximations and randomization to boost CSP techniques. Zbl 1062.90033
Gomes, Carla P.; Shmoys, David B.
3
2004
An improved approximation algorithm for the partial Latin square extension problem. Zbl 1078.68160
Gomes, Carla P.; Regis, Rommel G.; Shmoys, David B.
1
2004
Improved approximation algorithms for the uncapacitated facility location problem. Zbl 1044.90056
Chudak, Fabián A.; Shmoys, David B.
66
2003
Fault-tolerant facility location. Zbl 1092.68737
Swamy, Chaitanya; Shmoys, David B.
8
2003
Lagrangian relaxation for the \(k\)-median problem: new insights and continuity properties. Zbl 1266.90117
Archer, Aaron; Rajagopalan, Ranjithkumar; Shmoys, David B.
7
2003
An improved approximation algorithm for the partial latin square extension problem. Zbl 1141.68659
Gomes, Carla P.; Regis, Rommel G.; Shmoys, David B.
2
2003
A constant-factor approximation algorithm for the \(k\)-median problem. Zbl 1023.90037
Charikar, Moses; Guha, Sudipto; Tardos, Éva; Shmoys, David B.
41
2002
Approximation algorithms for facility location problems. Zbl 0976.68538
Shmoys, David B.
18
2000
Approximation algorithms for facility location problems. (Extended abstract). Zbl 0962.68008
Shmoys, David B.; Tardos, Éva; Aardal, Karen
128
1999
A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract). Zbl 1346.68253
Charikar, Moses; Guha, Sudipto; Tardos, Éva; Shmoys, David B.
113
1999
A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem. Zbl 0994.90090
Aardal, Karen; Chudak, Fabián A.; Shmoys, David B.
37
1999
Improved approximation algorithms for a capacitated facility location problem. Zbl 1052.90580
Chudak, Fabián A.; Shmoys, David B.
18
1999
Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. Zbl 0923.68012
Chudak, Fabián A.; Shmoys, David B.
17
1999
Using linear programming in the design and analysis of approximation algorithms: Two illustrative problems. Zbl 0907.90186
Shmoys, David B.
4
1998
Improved bounds on relaxations of a parallel machine scheduling problem. Zbl 0911.90219
Phillips, Cynthia A.; Schulz, Andreas S.; Shmoys, David B.; Stein, Cliff; Wein, Joel
3
1998
Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Zbl 0883.90064
Hall, Leslie A.; Schulz, Andreas S.; Shmoys, David B.; Wein, Joel
100
1997
Short shop schedules. Zbl 0890.90112
Williamson, D. P.; Hall, L. A.; Hoogeveen, J. A.; Hurkens, C. A. J.; Lenstra, J. K.; Sevast’janov, S. V.; Shmoys, D. B.
56
1997
Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. Zbl 1321.68497
Chudak, Fabián A.; Shmoys, David B.
4
1997
Scheduling to minimize average completion time: Off-line and on-line algorithms. Zbl 0845.90071
Hall, Leslie A.; Shmoys, David B.; Wein, Joel
26
1996
Improved scheduling algorithms for minsum criteria (extended abstract). Zbl 1046.68505
Chakrabarti, Soumen; Phillips, Cynthia A.; Schulz, Andreas S.; Shmoys, David B.; Stein, Cliff; Wein, Joel
25
1996
A new approach to computing optimal schedules for the job-shop scheduling problem. Zbl 1414.90162
Martin, Paul; Shmoys, David B.
12
1996
Fast approximation algorithms for fractional packing and covering problems. Zbl 0837.90103
Plotkin, Serge A.; Shmoys, David B.; Tardos, Éva
62
1995
Scheduling parallel machines on-line. Zbl 0845.68042
Shmoys, David B.; Wein, Joel; Williamson, David P.
40
1995
Computing near-optimal solutions to combinatorial optimization problems. Zbl 0835.90081
Shmoys, David B.
3
1995
Computational complexity. Zbl 0844.68046
Shmoys, D. B.; Tardos, É.
1
1995
Improved approximation algorithms for network design problems. Zbl 0873.68005
Goemans, M. X.; Goldberg, A. V.; Plotkin, S.; Shmoys, D. B.; Tardos, É.; Williamson, D. P.
50
1994
Improved approximation algorithms for shop scheduling problems. Zbl 0814.68026
Shmoys, David B.; Stein, Clifford; Wein, Joel
35
1994
An approximation algorithm for the generalized assignment problem. Zbl 0804.90077
Shmoys, David B.; Tardos, Éva
92
1993
Scheduling unrelated machines with costs. Zbl 0801.68014
Shmoys, David B.; Tardos, Éva
10
1993
Jackson’s rule for single-machine scheduling: Making a good heuristic better. Zbl 0781.90052
Hall, Leslie A.; Shmoys, David B.
43
1992
Scheduling parallel machines on-line. Zbl 0800.68214
Shmoys, David B.; Wein, Joel; Williamson, David P.
7
1992
Using interior-point methods for fast parallel algorithms for bipartite matching and related problems. Zbl 0743.68074
Goldberg, Andrew V.; Plotkin, Serge A.; Shmoys, David B.; Tardos, Eva
2
1992
Permutation vs. non-permutation flow shop schedules. Zbl 0742.90045
Potts, Chris N.; Shmoys, David B.; Williamson, David P.
23
1991
Improved approximation algorithms for shop scheduling problems. Zbl 0800.68222
Shmoys, David B.; Stein, Clifford; Wein, Joel
9
1991
Approximation algorithms for scheduling unrelated parallel machines. Zbl 0715.90063
Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva
175
1990
Analyzing the Held-Karp TSP bound: A monotonicity property with application. Zbl 0698.68050
Shmoys, David B.; Williamson, David P.
28
1990
Flipping persuasively in constant time. Zbl 0698.68043
Dwork, Cynthia; Shmoys, David; Stockmeyer, Larry
7
1990
Simple constant-time consensus protocols in realistic failure models. Zbl 0675.90038
Chor, Benny; Merritt, Michael; Shmoys, David B.
4
1989
The parallel complexity of TSP heuristics. Zbl 0679.68086
Kindervater, Gerard A. P.; Lenstra, Jan Karel; Shmoys, David B.
3
1989
A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach. Zbl 0647.68040
Hochbaum, Dorit S.; Shmoys, David B.
68
1988
Efficient parallel algorithms for edge coloring problems. Zbl 0642.68125
Karloff, Howard J.; Shmoys, David B.
10
1987
A better than ”best possible” algorithm to edge color multigraphs. Zbl 0594.68041
Hochbaum, Dorit S.; Nishizeki, Takao; Shmoys, David B.
10
1986
Best possible heuristics for the bottleneck wandering salesperson and bottleneck vehicle routing problem. Zbl 0596.90093
Hochbaum, Dorit S.; Shmoys, David B.
2
1986
A polynomial approximation scheme for machine scheduling on uniform processors: Using the dual approximation approach. Zbl 0623.68033
Hochbaum, Dorit S.; Shmoys, David B.
1
1986
The traveling salesman problem. A guided tour of combinatorial optimization. Reprint. Zbl 0562.00014
Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G.; Shmoys, D. B.
181
1985
The traveling salesman problem. Bibliography. Zbl 0563.90075
Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G.; Shmoys, D. B.
147
1985
A best possible heuristic for the k-center problem. Zbl 0565.90015
Hochbaum, Dorit S.; Shmoys, David B.
92
1985
Well-solved special cases. Zbl 0631.90081
Gilmore, P. C.; Lawler, E. L.; Shmoys, D. B.
65
1985
An \(O(| V| ^ 2)\) algorithm for the planar 3-cut problem. Zbl 0572.05040
Hochbaum, Dorit S.; Shmoys, David B.
4
1985
Recognizing graphs with fixed interval number is NP-complete. Zbl 0554.68041
West, Douglas B.; Shmoys, David B.
22
1984
all top 5

Cited by 2,732 Authors

51 Xu, Dachuan
31 Woeginger, Gerhard Johannes
25 Jansen, Klaus
25 Williamson, David P.
24 Du, Donglei
21 Wu, Chenchen
16 Sviridenko, Maxim I.
15 Leung, Joseph Y.-T.
15 Mastrolilli, Monaldo
15 Shmoys, David B.
13 Levin, Asaf
13 Nagarajan, Viswanath
13 Punnen, Abraham P.
13 Zhang, Dongmei
12 Kortsarz, Guy
11 Burkard, Rainer E.
11 Deĭneko, Vladimir G.
11 Epstein, Leah
11 Nutov, Zeev
11 Svensson, Ola
10 Byrka, Jarosław
10 Levi, Retsef
10 Sitters, Rene A.
10 Solis-Oba, Roberto
10 Wiese, Andreas
9 Azar, Yossi
9 Chrobak, Marek
9 Gouveia, Luis
9 Kumar, Amit
9 Lin, Guohui
9 Pinedo, Michael L.
9 Strusevich, Vitaly A.
9 Trystram, Denis R.
8 Bampis, Evripidis
8 Bansal, Nikhil
8 Goemans, Michel X.
8 Gupta, Anupam
8 Khandekar, Rohit
8 Khuller, Samir
8 Lee, Kangbok
8 Sevastyanov, Sergeĭ Vasil’evich
8 Srinivasan, Aravind
8 Verschae, José
7 Angel, Eric
7 Chekuri, Chandra S.
7 Kellerer, Johann
7 Klinz, Bettina
7 Kolliopoulos, Stavros G.
7 Krumke, Sven Oliver
7 Laporte, Gilbert
7 Leonardi, Stefano
7 Rawitz, Dror
7 Segev, Danny
7 Sgall, Jiří
7 Shabtay, Dvir
7 Stougie, Leen
7 van Zuylen, Anke
7 Vygen, Jens
7 Wang, Yishui
7 Xu, Yinfeng
7 Yuan, Jinjiang
6 Bertsimas, Dimitris John
6 Bonifaci, Vincenzo
6 Gørtz, Inge Li
6 Kononov, Alexander V.
6 Kurpisz, Adam
6 Li, Yu
6 Marchetti-Spaccamela, Alberto
6 Miyano, Eiji
6 Peleg, David
6 Potts, Chris N.
6 Shachnai, Hadas
6 Shen, Zuo-Jun Max
6 Skutella, Martin
6 Stein, Clifford
6 Topaloglu, Huseyin
6 Vakhania, Nodari N.
6 Zhang, Guochuan
5 Chakrabarty, Deeparnab
5 Chao, Xiuli
5 Chen, Bo
5 Chen, Lin
5 Christodoulou, George C.
5 Chu, Chengbin
5 Chudak, Fabián A.
5 Correa, José R.
5 Dong, Jianming
5 Fotakis, Dimitris A.
5 Hajiaghayi, Mohammad Taghi
5 Hochbaum, Dorit S.
5 Kacem, Imed
5 Li, Shuguang
5 Maack, Marten
5 Mestre, Julián
5 Milis, Ioannis
5 Niedermeier, Rolf
5 Pardalos, Panos M.
5 Paschos, Vangelis Th.
5 Pedrosa, Lehilton L. C.
5 Pesch, Erwin
...and 2,632 more Authors
all top 5

Cited in 182 Serials

161 European Journal of Operational Research
131 Theoretical Computer Science
111 Operations Research Letters
104 Discrete Applied Mathematics
93 Algorithmica
82 Mathematical Programming. Series A. Series B
81 Computers & Operations Research
58 Journal of Scheduling
51 Information Processing Letters
51 Journal of Combinatorial Optimization
42 Operations Research
31 Annals of Operations Research
29 Discrete Optimization
22 Mathematics of Operations Research
22 Theory of Computing Systems
21 Journal of Computer and System Sciences
21 Networks
17 SIAM Journal on Computing
14 International Journal of Foundations of Computer Science
13 Discrete Mathematics
13 Journal of Discrete Algorithms
13 Optimization Letters
12 Mathematical and Computer Modelling
12 Journal of Global Optimization
11 INFORMS Journal on Computing
10 Naval Research Logistics
10 SIAM Journal on Discrete Mathematics
10 Distributed Computing
9 Information Sciences
9 Mathematical Problems in Engineering
8 Asia-Pacific Journal of Operational Research
8 Journal of Parallel and Distributed Computing
8 Computational Optimization and Applications
8 Journal of Heuristics
7 Applied Mathematics and Computation
7 Games and Economic Behavior
7 Journal of the Operations Research Society of China
6 Artificial Intelligence
6 Opsearch
6 International Journal of Production Research
6 Acta Mathematicae Applicatae Sinica. English Series
6 Discrete & Computational Geometry
6 4OR
5 Journal of Information & Optimization Sciences
5 Combinatorica
5 Automation and Remote Control
5 RAIRO. Operations Research
5 Journal of Systems Science and Complexity
5 Journal of Industrial and Management Optimization
5 Proceedings of the Steklov Institute of Mathematics
5 Algorithms
4 International Journal of Systems Science
4 Computing
4 Journal of Computational and Applied Mathematics
4 Optimization
4 Applied Mathematics Letters
4 Real-Time Systems
4 SIAM Journal on Optimization
4 International Transactions in Operational Research
4 Optimization Methods & Software
4 Mathematical Methods of Operations Research
4 Discrete Mathematics, Algorithms and Applications
4 Computer Science Review
3 Acta Informatica
3 Journal of Statistical Physics
3 The Annals of Statistics
3 Journal of Optimization Theory and Applications
3 Information and Computation
3 International Journal of Computational Geometry & Applications
3 Applied Mathematical Modelling
3 Top
3 CEJOR. Central European Journal of Operations Research
3 Quantum Information Processing
3 Mathematical Programming Computation
2 Biological Cybernetics
2 Journal of Mathematical Analysis and Applications
2 Chaos, Solitons and Fractals
2 Automatica
2 Journal of Combinatorial Theory. Series B
2 Journal of Soviet Mathematics
2 Mathematica Slovaca
2 Queueing Systems
2 Computational Geometry
2 Discrete Event Dynamic Systems
2 Computational Statistics
2 Computational Mathematics and Mathematical Physics
2 Linear Algebra and its Applications
2 Computational Statistics and Data Analysis
2 Journal of Computer and Systems Sciences International
2 SIAM Journal on Scientific Computing
2 Combinatorics, Probability and Computing
2 International Journal of Computer Vision
2 Annals of Mathematics and Artificial Intelligence
2 Complexity
2 Constraints
2 Journal of Mathematical Chemistry
2 Parallel Algorithms and Applications
2 Journal of Applied Mathematics
2 OR Spectrum
2 Computational Management Science
...and 82 more Serials

Citations by Year

Wikidata Timeline

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.