On-Line Competitive Algorithms

在线竞争算法

• 批准号: 9503498
• 负责人: Marek Chrobak
• 金额: $ 14.67万
• 依托单位: University of California-Riverside
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-04-01 至 1998-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9503498&HistoricalAwards=false
• 关键词: Line; Competitive; Algorithms

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.

这个项目的重点是与在线问题相关的一些主题。在线算法只处理输入数据的部分信息。在每个时间步，这样的算法接收一个数据单元，并且必须在看到剩余数据之前产生部分结果。在线竞争算法是指返回的解不差于最优解的常数倍的算法。目标之一是解决k-server问题。已经开发了k台服务器的最优算法：该算法对两台服务器是2竞争的。一个封闭形式的函数，它是一个很好的候选的势函数k = 3，进行了研究。第二个目标是解决一些其他在线问题，其中最优竞争是未知的，包括：随机列表更新、多处理器调度和页面迁移；并发展在线问题解决的一般理论。第三个目标是展示为解决k-server问题而开发的技术如何应用于其他联机问题。特别地，开发了功函数、宽恕和稳定分布在一般在线问题中的应用。注：这是UNLV的CCR-9503441 （PI: Larmore）的同伴奖。