In on-line problems (as opposed to batch), you are presented with
tasks to complete, one at a time, each of which must be completed
before the next one. State is restricted. Examples:
- Paging
- Caching
- Data structures (e.g. search tree)
- Scheduling (disk, jobs)
- Distributed/Replicated files
- Bin Packing
- ...
In Competitive Analysis we
compare the performance of a proposed on-line algorithm with
the performance of the off-line optimum. Try to minimize ratio.
This approach has led to many new algorithms, as well as many new
open problems.