算法高级教程3.10Onlinealgorithms.pptVIP

* Online algorithms Typically when we solve problems and design algorithms we assume that we know all the data a priori. However in many practical situations this may not be true and rather than have the input in advance it may be presented to us as we proceed. Input is revealed to the algorithm incrementally Output is produced incrementally Some output must be produced before the entire input is known to the algorithm Decision making under partial information Unknown information: the future * Applications Resource Allocation Scheduling Memory Management Robot Motion Planning Exploring an unknown terrain Finding a destination Computational Finance * How to evaluate the performance of online algorithms One way to analyze such algorithms is to assume that the input is given according to a certain probability distribution and compute the expected behavior of the algorithm based on this distribution. However we wish to avoid making assumptions about input distributions. The analytic machinery we present will not demand that the inputs come from some known distribution but instead will compare the performance of the online algorithm with that of the best online algorithm. * Methods of Analysis Probabilistic Analysis Assume a distribution generating the input Find an algorithm which minimizes the expected cost of the algorithm. Need to accurately determine the true distribution generating the request sequence Probability distribution generating input sequence is “non-adaptive” (i.e. determined in advance and is independent of the choices made by the algorithm). * Methods of Analysis Worst Case Analysis For any input, the cost of our online algorithm is never worse than “R” times the cost of the optimal offline algorithm. Definition An online algorithm A is R-competitive if for all input sequences I, A(I) ≤ROPT(I), where A(I) is the cost of the online strategy A for I and OPT(I) is the cost of the optimal offline algorithm for I. In many cases the definition of competit