On-line Competitive Algorithms

在线算法只处理输入数据的部分信息。在每个时间步，这样的算法接收一个数据单元，并且必须在看到剩余数据之前产生部分结果。这个项目将专注于在线竞争算法，这是一种算法，它返回的解不差于最优解的常数倍。在k-server问题中，一个在线请求序列必须由k个在度量空间中移动的服务器中的一个来满足。服务器算法的成本被定义为服务器的总移动。本文将从网络游戏的角度阐述解决网络问题的一般方法。在这项工作中开发的技术应该在其他在线问题中找到应用。

On-line algorithms work with only partial information about the input data. At each time step, such an algorithm receives one unit of data, and has to produce partial results before seeing the remaining data. This project will focus on on-line competitive algorithms, which are algorithms that return a solution that is not worse than a constant times the optimal one. In the k-server problem, an on-line sequence of requests must each be met by one of k servers which move around in a metric space. The cost of a server algorithm is defined to be the total movement of the servers. General methods for solving on-line problems will be formulated in terms of on-line games. The techniques developed in this work should find applications in other on-line problems.