On-line Algorithms

点击翻译按钮获取中文摘要

This research project, in the area of on-line algorithms, focuses on deterministic and randomized algorithms for the k-server problem and some natural generalizations of it. Many important questions related to these problems are examined. Their resolution will impact the area of on-line algorithms, and will help to bridge the gap between the theory of competitive analysis and its numerous applications in robotics, data and memory management and programming languages. Additional areas of investigation include complexity theory, the theory of circuits, approximation algorithms, and novel search strategies.