|
Selected Recent Research Papers
Approximation Algorithms for Stochastic Programming Problems
R. Levi, M. Pal, R. Roundy, and D. Shmoys.
"Approximation algorithms for stochastic inventory control models,"
to appear in Mathematics of Operations Research.
.pdf file of journal version
Preliminary version appeared in
Proceedings of the 11th MPS
Conference on Integer Programming and Combinatorial Optimization, 2005,
306-320.
D.B. Shmoys and C. Swamy. "An approximation scheme for stochastic linear
programming and its application to stochastic integer programs."
To appear in Journal of the ACM.
.pdf version
Preliminary version appeared as "Stochastic Optimization is (almost) as
Easy as Deterministic Optimization" in Proceedings of FOCS 2004, pages 228-237.
C. Swamy and D.B. Shmoys. "Sampling-based approximation algorithms for
multi-stage stochastic optimization."
In Proceedings of FOCS 2005, pages 357-366.
.ps version
R. Levi, V.A. Truong, R. Roundy, and D.B. Shmoys. "Approximation
algorithms for capacitated stochastic inventory control problems."
Submitted for publication.
R. Levi, R. Roundy, and D.B. Shmoys.
"Provably near-optimal sampling-based policies for stochastic inventory
control models."
To appear in Mathematics of Operations Research.
.pdf file of journal version
Preliminary version appeared in Proceedings of STOC 2006, 739-748.
Approximation Algorithms for Deterministic Inventory Models
R. Levi, J. Geunes, E. Romeijn, and D.B. Shmoys.
"Inventory and facility-location models with market selection,"
Proceedings of the 11th MPS
Conference on Integer Programming and Combinatorial Optimization, 2005, 111-124.
.ps version.
R. Levi, R. Roundy, and D.B. Shmoys.
"A constant approximation algorithm for the one-warehouse-multi-retailer
problem,"
Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms,
2005, 365-374.
.pdf version
R. Levi, R. Roundy, and D.B. Shmoys.
"Primal-dual algorithms for deterministic inventory problems,"
Mathematics of Operations Research 31, 2006, 267-284.
.pdf file of journal version
Preliminary version appeared in
Proceedings of the 36th Annual Symposium on Theory of Computing, 2004,
353-362.
Approximation Algorithms for Facility Location Problems
R. Levi, D.B. Shmoys, and C. Swamy.
"LP-based approximation algorithms for capacitated facility location," in
Proceedings of the 10th MPS Conference on Integer Programming and
Combinatorial Optimization}, 2004, 206-218.
.ps version
A. Archer, R. Rajagopalan, D.B. Shmoys.
"Lagrangian relaxation for the k-median problem: new insights and
continuity properties," in
Proceedings of the 11th Annual European Symposium on Algorithms,
2003, 31--42.
.ps version
D.B. Shmoys, C. Swamy and R. Levi.
"Facility location with service installation costs," in
Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms,
2004, 1081-1090.
.ps version
C. Swamy and D.B. Shmoys.
"Fault-tolerant facility location".
Proceedings 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 2003,
735-736.
.ps version.
F.A. Chudak and D.B Shmoys.
"Improved approximation algorithms for the uncapacitated facility location
problem". SIAM J. on Computing 33, 2003, 1-25.
.ps version.
M. Charikar, S. Guha, E. Tardos, and D.B. Shmoys.
"A constant-factor approximation algorithm for the k-median problem".
Journal Computer System Sciences 65, 2002, 129-149.
.ps version.
K.I. Aardal, F.A. Chudak, and D.B. Shmoys.
"Improved approximation algorithms for the k-level facility location
problem". Information Processing Letters 72, 1999, 161-167.
.ps version.
F.A. Chudak and D.B. Shmoys.
"Improved approximation algorithms for the capacitated facility location
problem". In the Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete
Algorithms, 1999, S875-S876.
Algorithms for Sequencing and Scheduling Problems
L.A. Hall, A. S. Schulz, D.B. Shmoys, and J. Wein.
"Scheduling to minimize average completion time: off-line and on-line
approximation algorithms". Mathematics of Operations Research 22, 1997, 513-544.
.ps version.
F.A. Chudak and D.B. Shmoys. "Approximation algorithms for
precedence-constrained scheduling problems on parallel machines that
run at different speeds". J. Algorithms 30, 323-343.
[Special issue of selected papers from the 8th Annual
ACM-SIAM Symposium on Discrete Algorithms.]
.ps version.
P. Martin and D.B. Shmoys. "A new approach to computing optimal
schedules for the job-shop scheduling problem". In Proceedings of the
5th International IPCO Conference (1996), 389-403.
paper.ps
tables.ps
L.A. Hall, D.B. Shmoys, and J. Wein.
"Scheduling to minimize average completion time: off-line and on-line
algorithms". In the Proceeding of the 7th Annual ACM-SIAM Symposium on Discrete
Algorithms (1996), 142-151.
D.B. Shmoys and E. Tardos, "An approximation algorithm for the
generalized assignment problem". Mathematical Programming A 62, 1993,
461-474.
Other Selected Recent Papers
C.P. Gomes, R.G. Regis, and D.B. Shmoys.
"An improved approximation algorithm for the partial latin square extension
problem". Operations Research Letters 32, 479-484. A preliminary version
appeared in Proceedings 14th Annual ACM-SIAM Symposium on Discrete
Algorithms, 2003, 832-833.
.ps version.
T.J. Vision, D.G. Brown, D.B. Shmoys, R.T. Durrett, and S.D. Tanksley.
Selective mapping: A strategy for optimizing the construction of linkage map.
Genetics 155: 407-420, 2000.
[ABSTRACT]
M.X. Goemans, A.V. Goldberg, S. Plotkin, D.B. Shmoys, E. Tardos, and D.P.
Williamson. "Improved approximation algorithms for network design
problems". In the Proceeding of the 5th Annual ACM-SIAM Symposium on Discrete
Algorithms (1994), 223-232.
ORIE TR-1116.
S.A. Plotkin, D.B. Shmoys, E. Tardos. "Fast approximation algorithms
for fractional packing and covering problems".
Mathematics of Operations Research 20, 1995, 257-301.
Preliminary version
appeared in the Proceedings of the 32nd Annual IEEE Symposium on the
Foundations of Computer Science (1991), 495-504.
ORIE TR-999.
Selected Survey Papers
D.B. Shmoys and E. Tardos, "Computational complexity".
In: The Handbook of Combinatorics
(R.L. Graham, M. Grotschel, and L. Lovasz, eds.), North Holland, 1995,
1599-1645. .ps versi
on
This was written during the period 1987-1990, and so is not as recent
a survey as its date suggests. Some pointers to more recent work were
included in the final stage of publication.
L. Lovasz, D.B. Shmoys and E. Tardos. "Combinatorics in computer
science". In: The Handbook of Combinatorics (R.L. Graham,
M.Grotschel, and L. Lovasz, eds.) North Holland, 1995, 2003-2038.
.ps version
D.B. Shmoys. "Computing near-optimal solutions to combinatorial
optimization problems". In: Combinatorial
Optimization, (W. Cook, L. Lovasz, and P.D. Seymour, eds.) AMS, 1995, 355-397.
ORIE TR-1120.
D.B. Shmoys. "[Approximation algorithms for] Cut problems and
their application to divide-and-conquer". In:
Approximation Algorithms for NP-hard Problems, (D.S. Hochbaum, ed.) PWS, 1997,
192-235. .ps version
A.S. Schulz, D.B. Shmoys, and D.P. Williamson. Approximation
algorithms. Proc. National Academy of Sciences 94, 1997, 12734-12735.
.pdf version
D.B. Shmoys. "Using linear programming in the design and analysis of
approximation algorithms: two illustrative problems". In:
Approximation Algorithms for Combinatorial Optimization,
Lecture Notes in Computer Science 1444
(K. Jansen and J. Rolim, eds.), Springer, Berlin, 1998, 15-32.
.ps version.
D.B. Shmoys. "Approximation algorithms for facility location problems".
In: Approximation Algorithms for Combinatorial Optimization,
Lecture Notes in Computer Science 1913,
(K. Jansen and S. Khuller, eds.), Springer, Berlin, 2000, 27-33.
.ps version.
D.B. Shmoys.
"The design and analysis of
approximation algorithms: facility location as a case study".
In: Trends in Optimization,
AMS Proceedings of Symposia in Applied Mathematics 61,
(S. Hosten, J. Lee, and R. Thomas, eds.), 2004, 85-97.
.ps version
C. Swamy and D.B. Shmoys.
"Approximation algorithms for 2-stage stochastic optimization problems."
In Proceedings in FSTTCS 2006, 5-19.
.pdf file.
|
 Vita
Current Courses
Research
Books
Publications
Current and Former PhD Students
Shmoys Home
Back to ORIE
|
