Online Algorithms
by
Susanne Albers
Dortmund University

Over the past decade, online algorithms have received a lot of research interest in the theoretical computer science community. In an online problem the input arrives incrementally, one piece at a time. In response to each input portion, an algorithm must generate output, not knowing future input. An online algorithm A is called c-competitive if, for all inputs, the solution computed by A is at most a factor of c away from the optimal solution. In this talk we survey classical as well as recent research results in the field.

Date received: March 30, 2001

Copyright © 2001 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafv-99.