Skip to main content
SpringerLink
Log in

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

  • Published:
Algorithmica Aims and scope Submit manuscript

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

References

  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, Dover: 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

Author information

Authors and Affiliations

  1. Department of Computer Science and Information Systems, The University of Hong Kong, Hong Kong

    Francis Y. L. Chin & Stanley P. Y. Fung

Authors
  1. Francis Y. L. Chin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Stanley P. Y. Fung
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Francis Y. L. Chin or Stanley P. Y. Fung.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chin, F., Fung, S. Online Scheduling with Partial Job Values: Does Timesharing or Randomization Help?. Algorithmica 37, 149–164 (2003). https://doi.org/10.1007/s00453-003-1025-6

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-003-1025-6

Search

Navigation