Skip to main content
SpringerLink
Log in

Online Algorithms

The State of the Art

  • Book
  • © 1998

Overview

Editors:
  1. Amos Fiat
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Gerhard J. Woeginger
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 1442)

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

Access this book

Log in via an institution
Softcover Book USD 89.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (17 chapters)

  1. Front Matter

    Download chapter PDF

  2. Competitive analysis of algorithms

    • Amos Fiat, Gerhard J. Woeginger
    Pages 1-12

  3. Self-organizing data structures

    • Susanne Albers, Jeffery Westbrook
    Pages 13-51

  4. Competitive analysis of paging

    • Sandy Irani
    Pages 52-73

  5. Metrical task systems, the server problem and the work function algorithm

    • Marek Chrobak, Lawrence L. Larmore
    Pages 74-96

  6. Distributed paging

    • Yair Bartal
    Pages 97-117

  7. Competitive analysis of distributed algorithms

    • James Aspnes
    Pages 118-146

  8. On-line packing and covering problems

    • János Csirik, Gerhard J. Woeginger
    Pages 147-177

  9. On-line load balancing

    • Yossi Azar
    Pages 178-195

  10. On-line scheduling

    • JiŘí Sgall
    Pages 196-231

  11. On-line searching and navigation

    • Piotr Berman
    Pages 232-241

  12. On-line network routing

    • Stefano Leonardi
    Pages 242-267

  13. On-line network optimization problems

    • Bala Kalyanasundaram, Kirk Pruhs
    Pages 268-280

  14. Coloring graphs on-line

    • Hal A. Kierstead
    Pages 281-305

  15. On-Line Algorithms in Machine Learning

    • Avrim Blum
    Pages 306-325

  16. Competitive solutions for on-line financial problems

    • Ran El-Yaniv
    Pages 326-372

  17. On the performance of competitive algorithms in practice

    • Anna R. Karlin
    Pages 373-384

  18. Competitive odds and ends

    • Amos Fiat, Gerhard J. Woeginger
    Pages 385-394

  19. Back Matter

    Download chapter PDF
Back to top

Keywords

About this book

This coherent anthology presents the state of the art in the booming area of online algorithms and competitive analysis of such algorithms. The 17 papers are carefully revised and thoroughly improved versions of presentations given first during a Dagstuhl seminar in 1996.
An overview by the volume editors introduces the area to the reader. The technical chapters are devoted to foundational and methodological issues for the design and analysis of various classes of online algorithms as well as to the detailed evaluation of algorithms for various activities in online processing, ranging from load balancing and scheduling to networking and financial problems. An outlook by the volume editors and a bibliography listing more than 750 references complete the work.
The book is ideally suited for advanced courses and self-study in online algorithms. It is indispensable reading for researchers and professionals active in the area.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation