Scheduling data transfers in a network and the set scheduling problem. (English) Zbl 1345.68030
Vitter, Jeffrey Scott (ed.) et al., Proceedings of the 31st annual ACM symposium on theory of computing, STOC 1999. Atlanta, GA, USA, May 1–4, 1999. New York, NY: ACM, Association for Computing Machinery (ISBN 1-58113-067-8). 189-197 (1999).
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 68M10 | Network design and communication in computer systems |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68W25 | Approximation algorithms |
| 90B18 | Communication networks in operations research |
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, and O. Waarts. On-line load balancing with applications to machine scheduling and virtual circuit routing. 25th A CM Symposium on Theory of Computing, pages 623-31, 1993. 10.1145/167088.167248 · Zbl 1310.68248 |
| [2] | B. Awerbuch, Y. Azar, and \(. Plotkin. Throughput competitive online routing. &tth IEEE symposium on Foundations of Computer Science, pages 32-40, 1993\) |
| [3] | Y. Bartal, \(. Leonardi, and A. Fiat. Lower bounds for on-line graph problems with applicat, ion to online circuit and optical routing. Proc. o/the ~8th Symposium on Theory of Computation, pages 531- 540, 1996. 10.1145/237814.23800\) · Zbl 0936.68073 |
| [4] | J.E, Beck and D.P. Siewiorek. Modeling multicomputer task allocation as a vector packing problem. 9th International Symposium on Systems Synthesis, pages 115-120, 1996. |
| [5] | M. Bender, S. Chakrabarti, and S. Muthukrishnan. Flow and stretch metrics for scheduling continuous job streams. Ninth Annual A CM-SIAM Symposium on Discrete Algorithms, pages 270-279, 1998. · Zbl 0929.68012 |
| [6] | S. Chakrabarti, C. Phillips, A. Schulz, D. Shmoys, C. Stein, and J. Wein. Improved scheduling algorithms for minsum criteria. 23rd l ternational Colloquium on Automata, Languages, and Programming, 1996. · Zbl 1046.68505 |
| [7] | C. Chekuri and S. Khanna. On multi-dimensional packing problems. Tenth A ’M-\(IAM Symposium on Discrete Algorithms, 1999\) · Zbl 0938.68067 |
| [8] | C. Chekuri, R. Motwani, B. Natarajan, and C. Stein. Approximation techniques for average completion time scheduling. Eighth Annual A CM- SIAM Symposium on Discrete Algorithms, pages 609-618, 1997. · Zbl 1321.68496 |
| [9] | U. Fetge and J. Kilian. Zero knowledge and the chromatic number. Proceedings of the Eleventh Annual Conference on Complexity Theory, IEEE, 1996. |
| [10] | A. Feldmann, M. Kao, J. Stall, and S. Tent. Optimal online scheduling of parallel jobs with dependencies. J. of Combinatorial Optimization, 1(4):393-411, 1998. · Zbl 0897.90126 |
| [11] | J. Garay and I. Gopal. Call preemption in communication networks. IEEE INFOUOM, pages 1043- 1050, 1992. |
| [12] | J. Garay, I. Gopal, S. Kutten, Y. Mansour, and M. Yung. Efficient on-line call control algorithms. 2nd Annual Israel Conference on Theory of Computing and Systems, 1993. · Zbl 0866.68042 |
| [13] | M. Garofalakis and Y. Ioannidis. Scheduling issues in multimedia query optimization. A CM Computing Surveys, 27(4):590-592, 1995. 10.1145/234782.234797 |
| [14] | L.A. Hall, D.B. Shmoys, A.S. Schulz, and J. Wein. Scheduling to minimize average completion time: off-line and on-line approximation algorithms. Mathematics of Operations Research, 22:5t3-544, 1997. 10.1287/moor.22.3.513 · Zbl 0883.90064 |
| [15] | L.A. Hall, D.B. Shmoys, and J. Wein. Scheduling to minimize average completion time: off-line and on-line algorithms. 7th Annual A CM-SIAM Symposium on Discrete Algorithms, pages 142-151, 1996. · Zbl 0845.90071 |
| [16] | D. Hochbaum. Appro cimation algorithms for NP- hard problems. PWS Publishing Company, 1997. |
| [17] | H. Kellerer, T. Tau enhahn, and G.J. Woeginger. Approximability and non-approximabili y results for minimizing total flow time on a single machine. 28th A CM Symposium on Theory of Computing, pages 418-426, 1996. 10.1145/237814.237989 · Zbl 0915.90151 |
| [18] | S. Leonardi and D. Raz. Approximating total flow time on parallel machines. Twenty-Ninth Annual A CM Symposium on Theory of Computing, pages 110-119, 1997. 10.1145/258533.258562 · Zbl 0962.68007 |
| [19] | C. Phillips, C. Stein, E. Torng, and J. Wein. Critical scheduling via resource augmentation. 29th A CM Symposium on Theory of Computing, 1997. 10.1145/258533.258570 · Zbl 0990.68022 |
| [20] | C. Phillips, C. Stein, and J. Wein. Scheduling jobs that arrive over time. Lecture Notes in Computer Science 955, pages 290-301, Springer, Berlin. · Zbl 1502.68371 |
| [21] | P. Raghavan and C. Thompson. Randomized rounding. Combinatorica, 7:365-374, 1987. 10.1007/BF02579324 · Zbl 0651.90052 |
| [22] | J. Sgall. Randomized on-line scheduling of parallel jobs. J. of Algorithms, 21:149 .. 175, 1996. 10.1006/jagm.1996.0041 · Zbl 0857.68011 |
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.
