skip to main content
article
Free Access

On-line algorithms

Authors Info & Claims
Published:01 September 1999Publication History
First page image

References

  1. 1 S. Albers. Better bounds for online scheduling. In Proc. 29th Annual ACM Symp. on Theory of Computing, 130-139, 1997. Google ScholarGoogle Scholar
  2. 2 J. Aspnes, Y. Azar, A. Fiat, S. Plotkin and O. Waarts. On-line routing of virtual circuits with applications to load balancing and machine scheduling. Journal of the A CM, 44:486-504, 1997. Google ScholarGoogle Scholar
  3. 3 B. Awerbuch, Y. Azar and S. Plotkin. Throughput-competitive online routing. In 34th IEEE Symp. on Foundations of Computer Science, 32-40, 1993.Google ScholarGoogle Scholar
  4. 4 B. Awerbuch, Y. Bartal, A. Fiat and A. Ros6n. Competitive non-preemptive call control. In Proc. of 5th ACM-SIAM Syrup. on Discrete Algorithms, 312-320, 1994. Google ScholarGoogle Scholar
  5. 5 B. Awerbuch, R. Gawlick, T. Leighton and Y. Rabani. On-line admission control and circuit routing for high performance computing and communication. In Proc. of the 35th Annual IEEE Syrup. on Foundations of Computer Science, 412-423, 1994.Google ScholarGoogle Scholar
  6. 6 Y. Azar, A. Broder and A. Karlin. On-line load balancing. Proc. 36th IEEE Syrup. on Foundations of Computer Science, 218-225, 1992.Google ScholarGoogle Scholar
  7. 7 Y. Azar. On-line load balancing. In Online Algorithms: The State of the Art, edited by A. Fiat and G. Woeginger, Springer LNCS 1442, 178-195, 1998. Google ScholarGoogle Scholar
  8. 8 Y. Azar and L. Epstein. On-line load balancing with of temporary tasks on identical machines. In Proc. 5th Israeli Syrup. on Theory of Computing and Systems, 119-125, 1997. Google ScholarGoogle Scholar
  9. 9 Y. Azar, B. Kalyanasundaram, S. Plotkin. K. Pruhs amd O. Waarts. Online load balancing of temporary tasks. In Proc. of the 3rd Workshop on Algorithms and Data Structures, Springer LNCS, 119-130, 1993. Google ScholarGoogle Scholar
  10. 10 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. Google ScholarGoogle Scholar
  11. 11 Y. Bartal, A. Fiat and S. Leonardi. Lower bounds for on-line graph problems with application to on-line circuit and optical routing. In Proc. of the 28th A CM Syrup. on Theory of Computing, 531-540, 1996. Google ScholarGoogle Scholar
  12. 12 Y. Bartal and S. Leonardi. On-line routing in all-optical networks. In Proc. of the 2~th International Colloqium on Automata, Languages and Programming, Springer LNCS, Volume 1256, 516-526, 1997. Google ScholarGoogle Scholar
  13. 13 S. Ben-David, A. Borodin, R.M. Karp, G. Tardos and A. Wigderson. On the power of randomization in on-line algorithms. Algorithmica, 11:2-14,1994.Google ScholarGoogle Scholar
  14. 14 A. Blum. On-line algorithms in machine learning. In Online Algorithms: The State of the Art, edited by A. Fiat and G. Woeginger, Springer LNCS, Volume 1442, 306-325, 1998. Google ScholarGoogle Scholar
  15. 15 A. Borodin and Ran E1-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998. Google ScholarGoogle Scholar
  16. 16 A. Borodin, N. LiniM and M. Saks. An optimal on-line algorithm for metrical task systems. Journal of the ACM, 39:745-763, 1992. Google ScholarGoogle Scholar
  17. 17 A. Borodin, S. Irani, P. Raghavan and B. Schieber. Competitive paging with locality of reference. In Proc. 23rd Annual ACM Syrup. on Theory of Computing, 249-259, 1991. Google ScholarGoogle Scholar
  18. 18 N. Cesa-Bianchi, Y. Freund, D.P. Helbold, D. Haussler, R.E. Schapire and M.K. Warmuth. How to use expert advice. In Proc. 25th Annual ACM Syrup. on Theory of Computing, 382-391, 1993. Google ScholarGoogle Scholar
  19. 19 A. Chou, J. Cooperstock, R. E1 Yaniv, M. Klugerman and T. Leighton. The statistical adversary allows optimal money-making trading strategies. In Proc. 6th Annual ACM- SIAM Syrup. on Discrete Algorithms, 467-476, 1995. Google ScholarGoogle Scholar
  20. 20 A. Fiat and A.R. Karlin. Randomized and multipointer paging with locality of reference. In Proc. 27th Annual ACM Syrup. on Theory of Computing, 626-634, 1995. Google ScholarGoogle Scholar
  21. 21 A. Fiat and Z. Ros~n. Experimental studies of access graph based heuristics. In Proc. 8th ACM-SIAM Syrup. on Discrete Algorithms, 1997. Google ScholarGoogle Scholar
  22. 22 J. Garay, I.S. Gopal, S. Kutten, Y. Mansour and M. Yung. Efficient online call control algorithms. In Proc. 2nd Israel Syrup. on Theory of Computing and Systems, 285-293, 1993.Google ScholarGoogle Scholar
  23. 23 R. Gawlick, A. Kamath, S. Plotkin and K. Ramakrishnan. Routing and admission control of virtual circuits in general topology networks. Technical Report BL011212-940819- 19TM ATf~T Bell Laboratories, 1994.Google ScholarGoogle Scholar
  24. 24 T. Gormley and E. Torng. Bounded online problems. Manuscript, 1998.Google ScholarGoogle Scholar
  25. 25 R.L. Graham. Bounds for certain multiprocessor anomalies. Bell System Technical Journal, 45:1563-1581, 1966.Google ScholarGoogle Scholar
  26. 26 D.S. Hochbaum (Editor). Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, 1997. Google ScholarGoogle Scholar
  27. 27 S. Irani, A.R. Karlin and S. Phillips. Strongly competitive algorithms for paging with locality of reference. In Proc. 3rd Annual ACM-SIAM Symp. on Discrete Algorithms, 228-236, 1992. Google ScholarGoogle Scholar
  28. 28 D.R. Karger, S.J. Phillips and E. Torng. A better algorithm for an ancient scheduling problem. Journal of Algorithms, 20: 400-430, 1996. Google ScholarGoogle Scholar
  29. 29 A. Karlin, M. Manasse, L. Rudolph and D.D. Sleator. Competitive snoopy caching, Algorithmica, 3:79-119, 1988.Google ScholarGoogle Scholar
  30. 30 J. Kleinberg and 1~. Tardos. Disjoint paths in densely embedded graphs. In Proc. of the 36th Annual IEEE Symp. on Foundations of Computer Science, 52-61, 1995. Google ScholarGoogle Scholar
  31. 31 E. Koutsoupias and C.H. Papadimitriou. Beyond competitive analysis. In Proc. 34th Annual Symp. on Foundations of Computer Science, 394-400, 1994.Google ScholarGoogle Scholar
  32. 32 S. Leonardi, A. Marchetti-Spaccamela, A. Presciutti and A. Ros~n. On-line randomized cMl-control revisited. In Proc. of the 9th ACM-SIAM Syrup. on Discrete Algorithms, 223-232, 1998. Google ScholarGoogle Scholar
  33. 33 S. Leonardi. On-line network routing. In Online Algorithms: The State of the Art, edited by A. Fiat and G. Woeginger, Springer LNCS, Volume 1442, 242-267, 1998. Google ScholarGoogle Scholar
  34. 34 N. Littlestone and M.K. Warmuth. The weighted majority algorithm. Information and Computation, 108:212-261, 1994. Google ScholarGoogle Scholar
  35. 35 M.S. Manasse, L.A. McGeoch and D.D. Sleator. Competitive algorithms for on-line problems. In Proc. 20th Annual ACM Symp. on Theory of Computing, 322-33, 1988. Google ScholarGoogle Scholar
  36. 36 R. Motwani, S. Phillips and E. Torng. Non-clearvoyant scheduling. Proc. 4th Annual ACM- SIAM Symp. on Discrete Algorithms, 422-431, 1993. Google ScholarGoogle Scholar
  37. 37 R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. Google ScholarGoogle Scholar
  38. 38 P. Raghavan. A statistical adversary for on-line algorithms. In On-Line Algorithms, DI- MACS Series in Discrete Mathematics and Theoretical Computer Science, 79-83, 1991.Google ScholarGoogle Scholar
  39. 39 J. SgM1. On-line scheduling. In Online Algorithms: The State of the Art, edited by A. Fiat and G. Woeginger, Springer LNCS, Volume 1442, 198-231, 1998.Google ScholarGoogle Scholar
  40. 40 D. Shmoys, J. Wein and D.P. Williamson. Scheduling parallel machines on-line. SIAM Journal on Computing 24:1313-1331, 1995. Google ScholarGoogle Scholar
  41. 41 D.D. Sleator and R.E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28:202-208, 1985. Google ScholarGoogle Scholar

Recommendations

Comments

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Sign in

Full Access

  • Published in

    cover image ACM Computing Surveys
    ACM Computing Surveys  Volume 31, Issue 3es
    Sept. 1999
    77 pages
    ISSN:0360-0300
    EISSN:1557-7341
    DOI:10.1145/333580
    Issue’s Table of Contents

    Copyright © 1999 ACM

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    • Published: 1 September 1999
    Published in csur Volume 31, Issue 3es

    Permissions

    Request permissions about this article.

    Request Permissions

    Check for updates

    Qualifiers

    • article

PDF Format

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader