M. Charikar, S. Guha, E. Tardos, and D.B. Shmoys. "A constant-factor approximation algorithm for the k-median problem". Proceedings of the 31st Annual ACM Symposium on Theory of Computing (1999). To appear. .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. .ps version.
F.A. Chudak and D.B Shmoys. "Improved approximation algorithms for the uncapacitated facility location problem".
D.B. Shmoys, E. Tardos, and K.I. Aardal. "Approximation algorithms for facility location problems". In the Proceedings of the 29th Annual ACM Symposium on Theory of Computing (1997), 265-274. .ps version.
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". In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (1997), 581-590. .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. .ps version.
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.
D.B. Shmoys and E. Tardos, "An approximation algorithm for the
generalized assignment problem". Mathematical Programming A 62, 1993,
461-474.
Preliminary version appeared in the Proceedings of the 4th Annual ACM-SIAM
Symposium on Discrete Algorithms (1993), 448-454.
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 version
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 Schulz, A. S., 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. .ps version