AF: Small: Beyond Worst-Case Analysis in Approximation Algorithms, Algorithmic Mechanism Design and Online Algorithms

AF：小：超越近似算法、算法机制设计和在线算法中的最坏情况分析

• 批准号: 1016509
• 负责人: Anna Karlin
• 金额: $ 49.98万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-08-01 至 2014-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1016509&HistoricalAwards=false
• 关键词: AF; Small; Beyond; Worst; Case

In theoretical computer science, algorithms are usually evaluated with respect to their worst-case performance, whereas in other areas, average-case analysis is often used. Both of these approaches have drawbacks: worst-case analysis is overly pessimistic and average-case analysis often rests on unrealistic assumptions. To address these issues, a number of other analysis frameworks have been proposed including self-improving algorithms, smoothed analysis, instance-optimality, and algorithmic design based on a variety of data models. The objective of the project is to continue this line of research and develop techniques that go beyond worst-case analysis in the areas of approximation algorithms, algorithmic mechanism design and online algorithms. In the area of approximation algorithms for NP-hard problems, the project focuses on the development of approximation algorithms that achieve a kind of instance optimality. In the area of algorithmic mechanism design, the PI will continue to study the design and analysis of profit maximizing auctions in single-parameter environments and beyond. In the area of online algorithms, the PI will work to develop effective online algorithms for a fundamental and practical self-organizing data structure problem.Through the development of more effective and practical algorithms and a deeper understanding of the performance of these algorithms in practice, this research has the potential to impact a variety of subfields of computer science including artificial intelligence, systems and networking, data mining, and electronic commerce.

在理论计算机科学中，通常根据最坏情况的性能来评估算法，而在其他领域，通常使用平均情况分析。这两种方法都有缺点：最坏情况分析过于悲观，而平均情况分析往往基于不切实际的假设。为了解决这些问题，人们提出了许多其他分析框架，包括自我改进算法、平滑分析、实例最优性和基于各种数据模型的算法设计。该项目的目标是继续这一研究方向，并开发在近似算法、算法机制设计和在线算法领域超越最坏情况分析的技术。 在 NP 困难问题的近似算法领域，该项目重点开发实现某种实例最优性的近似算法。在算法机制设计领域，PI将继续研究单参数及其他环境下利润最大化拍卖的设计和分析。在在线算法领域，PI将致力于针对基本且实用的自组织数据结构问题开发有效的在线算法。通过开发更有效且实用的算法以及更深入地了解这些算法在实践中的性能，这项研究有可能影响计算机科学的各个子领域，包括人工智能、系统和网络、数据挖掘和电子商务。