On Line Competitive Algorithm

在线竞技算法

• 批准号: 9821009
• 负责人: Lawrence Larmore
• 金额: $ 11.39万
• 依托单位: University of Nevada Las Vegas
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-07-01 至 2003-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9821009&HistoricalAwards=false
• 关键词: Line; Competitive; Algorithm

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.

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