Online Algorithms
Lists
Only you see this
Abstract
ALL the algorithms we have studied so far receive their entire inputs at one time. We turn our attention to online algorithms, which receive and process the input in partial amounts. In a typical setting, an online algorithm receives a sequence of requests for service. It must service each request before it receives the next one. In servicing each request, the algorithm has a choice of several alternatives, each with an associated cost. The alternative chosen at a step may influence the costs of alternatives on future requests. Examples of such situations arise in data-structuring, resource-allocation in operating systems, finance, and distributed computing.
BibTeX
@inproceedings{motwani1995online,
author = {Rajeev Motwani and Prabhakar Raghavan},
title = {{Online Algorithms}},
booktitle = {Cambridge},
year = {1995},
doi = {10.1017/cbo9780511814075.014},
}Loading related content...