Self-organizing sequential search and Hilbert's inequalities

F. R.K. Chung; D. J. Hajela; P. D. Seymour

doi:10.1016/0022-0000(88)90025-6

Self-organizing sequential search and Hilbert's inequalities

F. R.K. Chung, D. J. Hajela, P. D. Seymour

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

Abstract

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 n/2 times that of the optimal order and this bound is the best possible. Hilbert'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.

Original language	English (US)
Pages (from-to)	148-157
Number of pages	10
Journal	Journal of Computer and System Sciences
Volume	36
Issue number	2
DOIs	https://doi.org/10.1016/0022-0000(88)90025-6
State	Published - Apr 1988
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Networks and Communications
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1016/0022-0000(88)90025-6

Cite this

@article{e0f66df855c647b38a7279da01d0da18,

title = "Self-organizing sequential search and Hilbert's inequalities",

abstract = "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 n/2 times that of the optimal order and this bound is the best possible. Hilbert'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.",

author = "Chung, {F. R.K.} and Hajela, {D. J.} and Seymour, {P. D.}",

year = "1988",

month = apr,

doi = "10.1016/0022-0000(88)90025-6",

language = "English (US)",

volume = "36",

pages = "148--157",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Self-organizing sequential search and Hilbert's inequalities

AU - Chung, F. R.K.

AU - Hajela, D. J.

AU - Seymour, P. D.

PY - 1988/4

Y1 - 1988/4

N2 - 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 n/2 times that of the optimal order and this bound is the best possible. Hilbert'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.

AB - 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 n/2 times that of the optimal order and this bound is the best possible. Hilbert'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.

UR - http://www.scopus.com/inward/record.url?scp=0023995533&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023995533&partnerID=8YFLogxK

U2 - 10.1016/0022-0000(88)90025-6

DO - 10.1016/0022-0000(88)90025-6

M3 - Article

AN - SCOPUS:0023995533

SN - 0022-0000

VL - 36

SP - 148

EP - 157

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 2

ER -

Self-organizing sequential search and Hilbert's inequalities

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this