On-Line Competitive Algorithms

在线竞争算法

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

AbstractPI: Marek ChrobakProposal Number: 9988360Institution: University of California-RiversideOptimization problems that arise in practice are often inherently (online); that is, the input data is not available prior to computation but, instead, is given as a sequence of requests each of which must be served before the next one is received. A classical example is the (catching) problem in two-level memory systems. Modern computer architectures enhance memory performance by storing the most frequently accessed data items in a cache, which is a small buffer memory with very short access time. When a requested item r is not in the cache -- an event referred to as a (fault) -- the caching algorithm stores r in the cache. If the cache is full, the algorithm needs to decide which item to evict from the cache to make room for r. This decision is made (online), without the knowledge of future requests. Naturally, the goal is to minimize the number of faults. Due to incomplete information, online algorithms cannot, in general, compute optimal solutions. This brings up the issue of performance evaluation: how do we tell good algorithms from bad ones? One measure of the quality of online algorithms is their (competitive ratio), defined as the maximum, over all request sequences, and of the ratios between the solution computed by the online algorithm and the optimal (offline) solution. Thus, an algorithm with competitive ratio, says, 1.5, always computes a solution that is within 50% of the minimum. This research deals with the competitive analysis of online algorithms and is divided into three projects. The first project is to study several known, specific online problems, including the k-server problem, file caching, and others. The objectives of this work are to develop efficient competitive algorithms for these problems and to establish matching lower bounds on their competitive ratios. More fundamental issues in competitive analysis are addressed in the second project. The main focus here is on the techniques for the design and analysis of online algorithms. The most promising, emerging ideas in this direction include the work-function algorithm (and its extensions) and the primal-dual method. Both of these techniques, as well as some other, have been successfully applied to specific online problems, but the mechanism behind their success is still poorly understood, and they still require an in-depth study to determine their applicability to other problems. The third project is to explore some extensions of the competitive analysis that have been recently introduced for the caching problem: access graphs, diffuse adversaries, and loose competitiveness. In addition to work on some remaining open problems in this area, this project will also focus on adapting these new models to online problems other than caching (for example, file migration), and, if appropriate, on designing and studying other problem-specific models.

摘要PI：Marek Chrobak提案编号：9988360机构：University of California RiversideOptimization在实践中出现的问题往往是固有的（在线）;也就是说，输入数据在计算之前是不可用的，而是作为一个请求序列给出的，每个请求都必须在下一个请求被接收之前被服务。一个经典的例子是两级记忆系统中的（捕捉）问题。现代计算机体系结构通过将最频繁访问的数据项存储在高速缓存中来增强存储器性能，高速缓存是具有非常短的访问时间的小缓冲存储器。 当所请求的项r不在该高速缓存中时--一个称为（故障）的事件--高速缓存算法将r存储在该高速缓存中。如果该高速缓存已满，则算法需要决定从该高速缓存中逐出哪个项，以便为r腾出空间。 这个决定是（在线）做出的，不知道未来的请求。当然，目标是尽量减少故障的数量。由于信息不完全，在线算法通常不能计算最优解。这就带来了性能评估的问题：我们如何区分好的算法和坏的算法？ 在线算法质量的一个度量是它们的（竞争比），定义为所有请求序列上的最大值，以及在线算法计算的解决方案与最佳（离线）解决方案之间的比率。因此，一个具有竞争比的算法，比如说，1.5，总是计算出一个在最小值的50%以内的解。本研究探讨线上演算法之竞争分析，并分为三个计画。 第一个项目是研究几个已知的，特定的在线问题，包括k服务器问题，文件缓存等。 这项工作的目标是为这些问题开发高效的竞争算法，并建立匹配的竞争比的下界。 第二个项目讨论了竞争分析中更基本的问题。这里的主要重点是在线算法的设计和分析技术。在这个方向上最有前途的新兴思想包括功函数算法（及其扩展）和原始对偶方法。这两种技术，以及其他一些，已成功地应用于特定的在线问题，但其成功背后的机制仍然知之甚少，他们仍然需要深入研究，以确定其适用于其他问题。 第三个项目是探索一些扩展的竞争分析，最近推出的缓存问题：访问图，扩散的对手，松散的竞争力。除了解决这一领域的一些未决问题外，该项目还将侧重于使这些新模型适用于缓存以外的在线问题（例如文件迁移），并酌情设计和研究其他特定问题的模型。