On randomized online scheduling. (English) Zbl 1192.68091
Proceedings of the thirty-fourth annual ACM symposium on theory of computing (STOC 2002), Montreal, Quebec, Canada, May 19–21, 2002. New York, NY: ACM Press (ISBN 1-581-13495-9). 134-143, electronic only (2002).
For the entire collection see [Zbl 1074.68502].
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 68W10 | Parallel algorithms in computer science |
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | S. Albers. Better bounds for online scheduling. SIAM Journal on Computing, 29:459-473, 1999.]] 10.1137/S0097539797324874 · Zbl 0943.68183 |
| [2] | Y. Bartal, A. Fiat, H. Karloff and R. Vohra. New algorithms for an ancient scheduling problem. Journal of Computer and System Sciences, 51:359-366, 1995.]] 10.1006/jcss.1995.1074 · Zbl 1295.90008 |
| [3] | Y. Bartal, H. Karloff and Y. Rabani. A better lower bound for on-line scheduling. Information Processing Letters, 50:113-116, 1994.]] 10.1016/0020-0190(94)00026-3 · Zbl 0807.68013 |
| [4] | B. Chen, A. van Vliet and G.J. Woeginger. A lower bound for randomized on-line scheduling algorithms. Information Processing Letters, 51:219-222, 1994.]] 10.1016/0020-0190(94)00110-3 · Zbl 0821.68011 |
| [5] | U. Faigle, W. Kern and G. Turan. On the performance of on-line algorithms for particular problems. Acta Cybernetica · Zbl 0689.68051 |
| [6] | R. Fleischer and M. Wahl. Online scheduling revisited. Proc. 8th Annual European Symposium on Algorithms, Springer LNCS, 2000.]] · Zbl 0974.68020 |
| [7] | G. Galambos and G. Woeginger. An on-line scheduling heuristic with better worst case ratio than Graham’s list scheduling. SIAM Journal on Computing, 22:349-355, 1993.]] 10.1137/0222026 · Zbl 0781.90051 |
| [8] | T. Gormley, N. Reingold, E. Torng and J. Westbrook. Generating adversaries for request-answer games. Proc. 11th ACM-SIAM Symposium on Discrete Algorithms, 564-565, 2000.]] · Zbl 0962.91001 |
| [9] | R.L. Graham. Bounds for certain multi-processing anomalies. Bell System Technical Journal, 45:1563-1581, 1966.]] · Zbl 0168.40703 |
| [10] | D.R. Karger, S.J. Phillips and E. Torng. A better algorithm for an ancient scheduling problem. Journal of Algorithms, 20:400-430, 1996.]] 10.1006/jagm.1996.0019 · Zbl 0844.68010 |
| [11] | S.S. Seiden. Online randomized multiprocessor scheduling. Algorithmica, 28:173-216, 2000.]] · Zbl 0961.68018 |
| [12] | S.S.Seiden. Barely random algorithms for multiprocessor scheduling. To appear in Journal of Scheduling.]] 10.1023/A:1022960526107 · Zbl 1154.90485 |
| [13] | J. Sgall. A lower bound for randomized on-line multiprocessor scheduling. Information Processing Letters, 63:51-55, 1997.]] 10.1016/S0020-0190(97)00093-8 · Zbl 1336.68107 |
| [14] | D.D. Sleator and R.E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28:202-208, 1985.]] 10.1145/2786.2793 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
