On-line Algorithms

在线算法

• 批准号: 9521606
• 负责人: Elias Koutsoupias
• 金额: $ 18万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-08-01 至 1999-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9521606&HistoricalAwards=false
• 关键词: line; Algorithms

This research project, in the area of on-line algorithms, focuses on deterministic and randomized algorithms for the k-server problem and some natural generalizations of it. Many important questions related to these problems are examined. Their resolution will impact the area of on-line algorithms, and will help to bridge the gap between the theory of competitive analysis and its numerous applications in robotics, data and memory management and programming languages. Additional areas of investigation include complexity theory, the theory of circuits, approximation algorithms, and novel search strategies.

该研究项目属于在线算法领域，重点关注 k 服务器问题的确定性和随机算法及其一些自然推广。 与这些问题相关的许多重要问题都得到了研究。 他们的解决方案将影响在线算法领域，并将有助于弥合竞争分析理论与其在机器人、数据和内存管理以及编程语言中的众多应用之间的差距。 其他研究领域包括复杂性理论、电路理论、近似算法和新颖的搜索策略。