|
|||
|
IMADA - Department of Mathematics and Computer Science |
|
An on-line algorithm gets its input in small pieces and each piece must be handled by the algorithm without knowledge about future pieces. Many problems are inherently on-line. The paging problem is a good example: we have two levels of memory; a large, slow memory and a smaller, fast memory. When a program is running it is normally not known from the beginning which pages will be needed. Hence, the problem of which pages to store in the fast memory must be solved on-line. The standard quality measure for on-line algorithms is the competitive ratio which is, roughly speaking, the worst case ratio of the on-line performance to the performance of an optimal off-line algorithm. This is analogous to the approximation ratio for approximation algorithms. However, comparing an on-line algorithm to an algorithm which knows the entire future seems unfair. Thus, the competitive ratio tends to give overly pessimistic results and often fails to distinguish algorithms which are known to perform differently in practice. The talk describes various variations of and alternatives to the competitive ratio. The running examples are the paging problem and two bin packing problems. Host: Kim Skak Larsen
SDU HOME | IMADA HOME | Previous Page Last modified: March 6, 2003. Joan Boyar (joan@imada.sdu.dk) |