Online Algorithms

在线算法

• 批准号: 0105752
• 负责人: Elias Koutsoupias
• 金额: $ 17.88万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-06-15 至 2004-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0105752&HistoricalAwards=false
• 关键词: Online; Algorithms

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.

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