On Line Competitive Algorithm

本研究关注在线算法，主要集中在两个问题上，概括了众所周知的开放问题。第一个问题是：给定任何一种在线算法，以及对计算能力、内存或信息流的任何一种特定限制，是否存在一种在线算法满足这种限制，并且仍然是最优的（在所有在线算法中）？第二个问题是随机化是否有助于解决双服务器问题。特别地，本项目引入了一种新的对在线算法信息流的限制，称为无轨性，并试图回答无轨在线算法的上述问题。我们还将在该领域的主要问题k-server猜想上花费一些精力。除了服务器问题外，本研究还将尝试解决一些未知最优竞争的其他在线问题，包括：随机列表更新、多处理器调度和页面迁移。PI（与Chrobak一起）开发的许多工具已经被他们和其他人成功地使用，包括工作函数、伪成本、竞争游戏和凸包。计算机模拟是研究中必不可少的工具。工作的主要组成部分是为问题类寻找额外的通用工具。

CCR-9821009LarmoreThis research concerns on-line algorithms and is focused on two problems, generalizing well-known open problems. The first is: the given any on-line algorithm and any specific kind of restriction on computational power memory or information flow, does there exist, an on-line algorithm that satisfies this restriction and is still optimal (among all on-line algorithms)? The second is the question whether randomization helps for the 2-server problem.In particular, the project introduces a new restriction on information flow for on-line algorithms called tracklessness and seeks to answer the above questions for trackless on-line algorithms.Some effort will also be expended on the major problem of the area, the k-server conjecture. Besides the server problem, the research will attempt to settle a number of other on-line problems for which optimal competitiveness is unknown, including: randomized list update, multiprocessor scheduling, and page migration.A number of tools developed by the PI (in conjunction with Chrobak) have been used successfully, by them and by others, including workfunctions, pseudocost, competitive games, and convex hulls. Computer simulations are an essential tool in the research. A major component of the work in finding additional generic tools for classes of problems.