On-line algorithms
Susanne Albers, Stefano Leonardi · ACM Computing Surveys · 1999
Over the past twelve years, online algorithms have received considerable research interest.Online problems had been investigated already in the seventies and early eighties but an extensive, systematic study started only when Sleator and Tarjan [41] suggested comparing an online algorithm to an optimal offline algorithm and Karlin, Manasse, Rudolph and Sleator [29] coined the term competitive analysis.