On-Line Competitive Algorithms

这个项目关注一些与在线问题有关的主题。在线算法只处理有关输入数据的部分信息。在每个时间步，这样的算法接收一个数据单元，并且在看到剩余数据之前必须产生部分结果。在线竞争算法是指返回的解不比最优解的常量倍差的算法。目标之一是解决k-服务器问题。已经提出了k个服务器的最优算法：该算法对两个服务器是2-竞争的。对于k=3的势函数，我们考察了一个闭合形式的函数。第二个目标是解决其他一些在未知情况下具有最优竞争力的在线问题，包括：随机列表更新、多处理器调度和页面迁移；并发展在线问题解决的一般理论。第三个目标是向Hoe展示为解决k-服务器问题而开发的技术可以应用于其他在线问题。特别地，发展了功函数、容错和稳定分布在一般在线问题中的应用。注：这是对联合国志愿人员组织CCR-9503441(PI：拉莫尔)的配套奖励。

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 in unknown, including: randomized list update, multi-processor scheduling, and page migration; and to develop a general theory of on-line problems solutions. A third goal is to show hoe 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-9503441 (PI: Larmore) of UNLV.