On-Line Competitive Algorithms

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

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.