References

1

N. Alon. A parallel algorithmic version of the Local Lemma. In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, pages 586-593, 1991.

2

J. Beck. An algorithmic approach to the Lovász Local Lemma I. Random Structures and Algorithms.

3

R. Koch, T. Leighton, B. Maggs, S. Rao, and A. Rosenberg. Work-preserving emulations of fixed-connection networks. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 227-240, May 1989.

4

E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys. Sequencing and scheduling: Algorithms and complexity. Technical Report BS-R8909, Centre for Mathematics and Computer Science, Amsterdam, The Netherlands, June 1989.

5

F. T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays Trees Hypercubes. Morgan Kaufmann, San Mateo, CA, 1992.

6

F. T. Leighton, B. M. Maggs, A. G. Ranade, and S. B. Rao. Randomized routing and sorting on fixed-connection networks. Journal of Algorithms. To appear.

7

T. Leighton, B. Maggs, and S. Rao. Fast algorithms for finding O(congestion + dilation) packet routing schedules. Manuscript in preparation.

8

T. Leighton, B. Maggs, and S. Rao. Universal packet routing algorithms. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 256-271. IEEE Computer Society Press, October 1988.

9

A. G. Ranade. How to emulate shared memory. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science, pages 185-194. IEEE Computer Society Press, October 1987.

10

S. V. Sevast'yanov. Bounding algorithm for routing problem with arbitrary paths and alternate servers. Kibernetika, 22(6):74-79, 1986. Translation in Cybernetics 22, pages 773-780.

11

D. B. Shmoys, C. Stein, and J. Wein. Improved approximation algorithms for shop scheduling problems. In Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 148-157, January 1991.

12

J. Spencer. Ten Lectures on the Probabilistic Method. SIAM, Philadelphia, PA, 1987.