Online Algorithms

在线计算涉及到逐步揭示输入的优化问题。在线算法的决策只基于过去，而不了解未来，这与股市投资者或探索未知环境的机器人决定下一步行动的方式非常相似。在许多领域，在信息不完全的情况下做出决策的问题自然会出现。在过去的十年中，在线算法领域的研究非常密集。尽管如此，一些基本问题仍未解决，新的应用也产生了一些重要问题。这个项目既解决了网上的老问题，也解决了网上的新问题。也许最重要的未解决的基本问题是k-server问题。目标是解决k-服务器猜想，并研究问题的其他变体，如k-taxi问题和CNN问题。另一个目标是设计和分析一个相关问题的竞争算法，欧几里得空间的在线匹配问题；这个问题的一些有趣的变体似乎在新的电子商务应用程序中起着核心作用。对于所有这些问题和许多其他问题，一个算法，广义功函数算法，似乎具有几乎最优的竞争比。这项研究解决了这一现象的根源。研究还涉及数据库标引的相关问题；实际应用程序的数据集的大小一直在急剧增加，因此良好的索引方案的重要性也在增加。竞争分析可以用来量化索引方案的性能受数据库变化的影响程度。最后，竞争分析技术是解决网络中特定博弈论问题的有用工具。

Online computation involves optimization problems for which the input isrevealed progressively. Online algorithms base their decisions only on thepast without knowledge of the future, much in the same way that a stockmarket investor or a robot that explores an unknown environment decideabout their next action. Naturally such problems of decision-making withincomplete information arise in many areas. During the last decaderesearch in the area of online algorithms has been very intensive. Still,some of the fundamental problems remain unresolved and important problemsarise from new applications. The project deals both with old and newonline problems.Perhaps the most important fundamental unsolved problem is the k-serverproblem. The objective is to settle the k-server conjecture and toinvestigate other variants of the problem such as the k-taxicab problemand the CNN problem. Another objective is to design and analyzecompetitive algorithms for a related problem, the online matching problemon Euclidean spaces; some interesting variants of the problem seem to playa central role in new e-commerce applications. For all these and manyother problems, one algorithm, the generalized Work Function Algorithm,seems to have almost optimal competitive ratio. The research addresses theroots of this phenomenon.Research deals also with the pertinent problem of indexing of databases;the size of datasets of real applications has been increasing dramaticallyand so does the importance of good indexing schemes. Competitive analysiscan be used to quantify how much the performance of indexing schemes isaffected by changes in a database. Finally, the techniques of competitiveanalysis are a useful tool to address specific game-theoretic problems innetworks.