Self-organizing sequential search and Hilbert's inequalities (Q1104755): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0022-0000(88)90025-6 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W4240430811 / rank | |||
Normal rank | |||
Revision as of 20:16, 19 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Self-organizing sequential search and Hilbert's inequalities |
scientific article |
Statements
Self-organizing sequential search and Hilbert's inequalities (English)
0 references
1988
0 references
In this paper we describe a general technique which can be used to solve an old problem in analyzing self-organizing sequential search. We prove that the average time required for the move-to-front heuristic is no more than \(\pi\) /2 times that of the optimal order and this bound is the best possible. Hilbet's inequalities will be used to derive large classes of inequalities some of which can be applied to obtain tight worst-case bounds for several self-organizing heuristics.
0 references
self-organizing sequential search
0 references
average time
0 references
move-to-front heuristic
0 references
Hilbet's inequalities
0 references
worst-case bounds
0 references
