Online Scheduling with Partial Job Values: Does Timesharing or Randomization Help?

1. A. V. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974.

2. S. Baruah, G. Koren, D. Mao, B. Mishra, A. Raghunathan, L. Rosier, D. Shasha and F. Wang, On the Competitiveness of On-Line Real-Time Task Scheduling, Real-Time Systems, 4 (1992), 125–144.

3. J. L. Bentley and A. C.-C. Yao, An Almost Optimal Algorithm for Unbounded Searching, Information Processing Letters, 5(3) (1976), 82–87.

   Google Scholar 

4. A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, New York, 1998.

5. E. Chang and C. Yap, Competitive Online Scheduling with Level of Service, Proceedings of the 7th Annual International Computing and Combinatorics Conference, pp. 453–462, 2001.

6. F. Y. L. Chin and S. P. Y. Fung, Online Scheduling with Partial Job Values and Bounded Importance Ratio, Proceedings of the International Computer Symposium, pp. 787–794, 2002.

7. M. Chrobak, L. Epstein, J. Noga, J. Sgall, R. van Stee, T. Tich\’y and N. Vakhania, Preemptive Scheduling in Overloaded Systems, to appear in Journal of Computer and System Sciences. A preliminary version appeared in Proceedings of the 29th International Colloqium on Automata, Languages and Programming, pp. 800–811, 2002.

8. C.-T. Ho, R. Agrawal, N. Megiddo and R. Srikant, Range Queries in OLAP Data Cubes, Proceedings of the ACM SIGMOD Conference on the Management of Data, pp. 73–88, 1997.

9. R. Janardan, On the Dynamic Maintenance of Maximal Points in the Plane, Information Processing Letters, 40(2) (1991), 59–64.

   Google Scholar 

10. A. Karlin, C. Kenyon and D. Randall, Dynamic TCP Acknowledgement and Other Stories about e/(e-1), Proceedings of the Symposium on the Theory of Computing, pp. 502–509, 2001.

11. G. Koren and D. Shasha, D^over: An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems, SIAM Journal on Computing, 24 (1995), 318–339.

    Google Scholar 

12. J. W. S. Liu, K.-J. Lin, W.-K. Shih, A. C.-S. Yu, J.-Y. Chung and W. Zhao, Algorithms for Scheduling Imprecise Computations, IEEE Computer, 24(5) (1991), 58–68.

    Google Scholar 

13. J. Sgall, Online Scheduling, in Online Algorithms: the State of the Art (A. Fiat and G. J. Woeginger, eds.), pp. 196–227, Springer-Verlag, New York, 1998.

14. D. Sleator and R. Tarjan, Amortized Efficiency of List Update and Paging Rules, Communications of the ACM, 28(2) (1985), 202–208.

15. A. C.-C. Yao, Probabilistic Computations: Toward a Unified Measure of Complexity, Proceedings of the 18th IEEE Symposium on Foundations of Computer Science, pp. 222–227, 1977.

Download references