Online Algorithms

Rajeev Motwani, Prabhakar RaghavanCambridge 1995 · DOI · OpenAlex

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...

Figure