Competitive analysis of algorithms

1. 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.

   Article  Google Scholar 

2. A. Borodin, N. Linial, and M. Saks. An optimal online algorithm for metrical task systems. In Proc. 19th Annual ACM Symposium on Theory of Computing, pages 373–382, 1987.

   Google Scholar 

3. T.M. Cover. Universal portfolios. Mathematical Finance, 1(1):1–29, January 1991.

   Google Scholar 

4. R. L. Graham. Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 45:1563–1581, 1966.

   Google Scholar 

5. D. S. Johnson. Near-optimal bin packing algorithms. PhD thesis, MIT, Cambridge, MA, 1973.

   Google Scholar 

6. D. S. Johnson. Fast algorithms for bin packing. J. Comput. System Sci., 8:272–314, 1974.

   Google Scholar 

7. D. S. Johnson. Private communication, 1998.

   Google Scholar 

8. A. Karlin, M. Manasse, L. Rudolph, and D. Sleator. Competitive snoopy caching. Algorithmica, 3(1):79–119, 1988.

   Article  MathSciNet  Google Scholar 

9. H. A. Kierstead and W. T. Trotter. An extremal problem in recursive combinatorics. Congressus Numerantium, 33:143–153, 1981.

   Google Scholar 

10. D.E. Knuth. The Art of Computer Programming; Volume 2: Seminumerical Algorithms. Addison-Wesley, 1st edition, 1968.

    Google Scholar 

11. M. Manasse, L. A. McGeoch, and D. Sleator. Competitive algorithms for online problems. In Proc. 20th Annual ACM Symposium on Theory of Computing, pages 322–333, 1988.

    Google Scholar 

12. C. H. Papadimitriou and M. Yannakakis. Shortest paths without a map. Theoretical Computer Science, 84:127–150, 1991.

    Article  Google Scholar 

13. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28:202–208, 1985.

    Article  Google Scholar 

14. Daniel D. Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. Journal of the ACM, 32:652–686, 1985.

    Article  Google Scholar 

15. D. R. Woodall. The bay restaurant — a linear storage problem. American Mathematical Monthly, 81:240–246, 1974.

    Google Scholar 

16. A. C. C. Yao. New algorithms for bin packing. J. Assoc. Comput. Mach., 27:207–227, 1980.

    Google Scholar 

Download references