Online Competitive Algorithms

实践中出现的优化问题往往本质上是在线的；也就是说，输入数据在计算之前是不可用的，而是作为一个请求序列给出的，必须在接收到下一个请求之前提供该序列。一个经典的例子是两级内存系统中的缓存问题。现代计算机架构通过将频繁访问的数据项存储在高速缓存（一种小型缓冲存储器）中来提高内存性能。存储在缓存中的内存位置可以被快速访问。对不在缓存中的内存位置的请求称为错误或未命中，并且需要更多的时间。在每次内存访问之后，在线缓存算法需要决定是否将请求的项放入缓存中，如果是，则从缓存中取出哪个项。目标是最小化缓存故障的数量。由于信息不完全，在线算法通常不能计算出最优解。这就引出了性能评估的问题：我们如何区分好算法和坏算法？在线算法质量的一个衡量标准是它们的竞争比，竞争比定义为在线算法计算的解决方案与最优（离线）解决方案之间的比率在所有请求序列中的最大值。因此，一个竞争比为1.5的算法，总是计算出一个在最小值的50%以内的解。本研究涉及在线算法的竞争分析。正在探索几个研究方向。第一个方向是研究在线算法设计和分析的一般技术。在这里，最有前途的想法包括功函数算法（及其扩展）和原始对偶方法。这两种技术以及其他一些技术已经成功地应用于特定的在线问题，但是它们成功背后的机制仍然知之甚少，并且它们仍然需要深入研究以确定它们对其他问题的适用性。另一个方向是研究竞争分析的几个扩展，包括访问图（用于缓存）、扩散对手、松散竞争和资源增加。这项工作的重点是与这些模型相关的一些开放问题，将这些模型应用于其他在线问题，以及设计新的问题特定模型。研究者还在继续研究竞争分析中的几个经典问题，包括k-服务器问题，几个版本的缓存和调度问题，k-中值问题等。这些努力的主要目标是为这些问题开发有效的竞争算法，并建立竞争比率的匹配下界。

Optimization problems that arise in practice are often inherentlyonline; that is, the input data is not available prior tocomputation but, instead, is given as a sequence of requestseach of which must be served before the next one is received.A classical example is the caching problem in two-level memorysystems. Modern computer architectures enhance memory performanceby storing frequently accessed data items in a cache, which isa small buffer memory. Memory locations stored in the cachecan be accessed quickly. Requests to memory locations that arenot in the cache are called faults or misses, and take muchmore time. After each memory access, an online caching algorithmneeds to decide whether to put the requested item in the cache,and if so, which item to evict from the cache. The objectiveis to minimize the number of cache faults.Due to incomplete information, online algorithms cannot, in general,compute optimal solutions. This brings up the issue of performanceevaluation: how do we tell good algorithms from bad ones? One measureof the quality of online algorithms is their competitive ratio,defined as the maximum, over all request sequences, of the ratiosbetween the solution computed by the online algorithm and the optimal(offline) solution. Thus, an algorithm with competitive ratio, say,1.5, always computes a solution that is within 50% of the minimum.This research deals with the competitive analysis of online algorithms.Several research directions are being explored. The first directionis to study general techniques for the design and analysis of onlinealgorithms. Here, the most promising ideas include thework-function algorithm (and its extensions) and the primal-dual method.Both of these techniques, as well as some other, have been successfullyapplied to specific online problems, but the mechanism behind theirsuccess is still poorly understood, and they still require an in-depthstudy to determine their applicability to other problems. Anotherdirection is to study several extensions of the competitive analysis,including access graphs (for caching), diffuse adversaries, loosecompetitiveness and resource augmentation. This work focuses on some openproblems related to these models, on adapting these models to otheronline problems, and on designing new problem-specific models. Theinvestigator is also continuing his work on several classicalproblems in competitive analysis, including the k-serverproblem, several versions of caching and scheduling problems,the k-median problem, and other. The main goals of these effortsare to develop efficient competitive algorithms for these problemsand to establish matching lower bounds on the competitive ratios.