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-Hard问题的近似算法领域，该项目专注于开发实现一种实例最优性的近似算法。在算法机制设计方面，PI将继续研究在单参数环境和其他环境下实现利润最大化拍卖的设计和分析。在在线算法领域，PI将致力于为一个基本和实用的自组织数据结构问题开发有效的在线算法。通过开发更有效和实用的算法，以及对这些算法在实践中的性能的更深入了解，这项研究有可能影响计算机科学的各个子领域，包括人工智能、系统与网络、数据挖掘和电子商务。