Online Computation and Competitive Analysis

摘要: Preface 1. Introduction to competitive analysis: the list accessing problem 2. randomized algorithms: 3. Paging: deterministic algorithms 4. 5. Alternative models for paging: beyond pure analysis 6. Game theoretic foundations 7. Request - answer games 8. Competitive and zero-sum 9. Metrical task systems 10. The k-server 11. Randomized 12. Load-balancing 13. Call admission circuit-routing 14. Search, trading portfolio selection 15. decision making under uncertainty Appendices Bibliography Index.