Self-organizing sequential search and Hilbert's inequalities

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

Research output: Contribution to journalArticle

13 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 languageEnglish (US)
Pages (from-to)148-157
Number of pages10
JournalJournal of Computer and System Sciences
Volume36
Issue number2
DOIs
StatePublished - Apr 1988
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'Self-organizing sequential search and Hilbert's inequalities'. Together they form a unique fingerprint.

  • Cite this