On-line Competitive Algorithms

这个项目的重点是一些与在线问题有关的主题。 在线算法只处理输入数据的部分信息。 在每个时间步，这样的算法接收一个数据单元，并且在看到剩余数据之前必须产生部分结果。 在线竞争算法是这样的算法，其返回的解不差于常数乘以最优解。 其中一个目标是解决k服务器问题。 已经开发了k个服务器的最优算法：该算法对于两个服务器是2-竞争的。 一个封闭的形式的功能，这是一个很好的候选人为k = 3的潜在功能，检查。 第二个目标是攻击一些其他的在线问题，其中最佳竞争力是未知的，包括：随机列表更新，多处理器调度，和页面迁移，并制定一个一般理论的在线问题的解决方案。 第三个目标是展示如何的技术，开发的K-服务器问题的解决方案，可以应用到其他在线问题。 特别是，应用程序的工作功能，宽恕和稳定的分布一般在线问题。 注：这是加州大学滨江分校CCR-9503498（PI：Chrobak）的同伴奖。

This project focuses on a number of topics related to on-line problems. 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. On-line competitive algorithms are algorithms which return a solution that is not worse than a constant times the optimal one. One of the goals is to solve the k-server problem. An optimal algorithm for k servers has already been developed: the algorithm is 2-competitive for two servers. A closed form function, which is a good candidate for the potential function for k = 3, is examined. A second goal is to attack a number of other on-line problems for which optimal competitiveness is unknown, including: randomized list update, multi-processor scheduling, and page migration; and to develop a general theory of on-line problem solutions. A third goal is to show how the techniques, developed for the solution of the k-server problem, can be applied to other on-line problems. In particular, applications of work functions, forgiveness and stable distributions to general on-line problems are developed. Note: This is a companion award to CCR-9503498 (PI: Chrobak) of University of California, Riverside.