Energy-efficient Algorithms

Over the past ten years, online algorithms have re-ceived considerable research interest. Online problems had been investigated already in the seventies and early eighties but an extensive, systematic study only started when Sleator and Tarjan (1985) suggested comparing an online algorithm to an optimal oine algorithm and Karlin, Manasse, Rudolph and Sleator (1988) coined the term competitive analysis. In this article we give an in-troduction to the theory of online algorithms and survey interesting application areas. We present important re-sults and outline directions for future research