Competitive algorithms for on-line problems

Published 1 January 1988

Mark S. Manasse, Lyle A. McGeoch, Daniel D. Sleator

Citations353

TL;DR

This paper presents several general results concerning competitive algorithms, as well as results on specific on-line problems.

Abstract

An on-line problem is one in which an algorithm must handle a sequence of requests, satisfying each request without knowledge of the future requests. Examples of on-line problems include scheduling the motion of elevators, finding routes in networks, allocating cache memory, and maintaining dynamic data structures. A competitive algorithm for an on-line problem has the property that its performance on any sequence of requests is within a constant factor of the performance of any other algorithm on the same sequence. This paper presents several general results concerning competitive algorithms, as well as results on specific on-line problems.

Keywords

Computer ScienceDecision SciencesEngineering

Communications of the ACMAmortized efficiency of list update and paging rules

2,109 Citations1985Daniel D. Sleator, Robert E. Tarjan

This article shows that move-to-front is within a constant factor of optimum among a wide class of list maintenance rules, and analyzes the amortized complexity of LRU, showing that its efficiency differs from that of the off-line paging rule by a factor that depends on the size of fast memory.

View PDF

AlgorithmicaCompetitive snoopy caching

612 Citations1988Anna R. Karlin, Mark S. Manasse +2 more

This work presents new on-line algorithms to be used by the caches of snoopy cache multiprocessor systems to decide which blocks to retain and which to drop in order to minimize communication over the bus.

An optimal online algorithm for metrical task systems

164 Citations1987Allan Borodin, Nathan Linial +1 more

A general model for the processing of sequences of tasks and a general online decision algorithm are introduced and it is shown that this algorithm is optimal among all online algorithms.

Communications of the ACMAmortized analyses of self-organizing sequential search heuristics

139 Citations1985Jon Bentley, Catherine C. McGeoch

Experiments show that the behavior of the heuristics on real data is more closely described by the amortized analyses than by the probabilistic analyses.

View PDF

Mathematics of Operations ResearchSequencing Problems in Two-Server Systems

43 Citations1985A.R. Calderbank, E. G. Coffman +1 more

A service system in which two identical servers move one at a time along a linear array of N positions is analyzed, and within a simple probability model server-selection policies are compared in terms of the equilibrium expected distance a server is moved in processing a request.

Communications in Statistics Stochastic ModelsSequencing two servers on a sphere

6 Citations1985A.R. Calderbank, E. G. Coffman +1 more

For all n the integral equation satisfied by the equilibrium measure for the angular distance Φ between servers under the nearer server (NS) policy is obtained, and the equation is solved numerically.