On-line Competitive Algorithms

在线算法只处理输入的部分信息 数据 在每个时间步，这样的算法接收一个数据单元， 并且在看到剩余数据之前必须产生部分结果。 该项目将侧重于在线竞争算法，这是 算法返回的解不比常数差 乘以最优值 在k服务器问题中， 每个请求必须由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.