Knowledge state algorithms (Q548658)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Knowledge state algorithms |
scientific article |
Statements
Knowledge state algorithms (English)
0 references
30 June 2011
0 references
The paper is concerned with constructing randomized online algorithms. The latter are able to process their input serially as the input is given and without knowing the entire input at the beginning. The authors coin the concept of a knowledge state algorithm that also covers several known types of algorithms. Optimality and competitiveness are studied.
0 references
online algorithms
0 references
competitive analysis
0 references
randomization
0 references