Learning, Algorithm Design and Beyond Worst-Case Analysis

学习、算法设计和超越最坏情况分析

• 批准号: 1639629
• 负责人: Richard Karp
• 金额: $ 2万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-07-01 至 2017-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1639629&HistoricalAwards=false
• 关键词: Learning; Algorithm; Design; Beyond; Worst

In computational complexity theory, the performance of an algorithm is traditionally defined by its worst-case resource usage as the size of the input tends to infinity. In practice, this asymptotic worst-case measure may be inappropriate for several reasons: the worst-case performance may occur only for contrived instances that never occur in practice; the instances occurring in practice may have special structural features; the average-case performance of the algorithm may be much better than its worst case; or heuristic algorithms may empirically be observed to perform well. The workshop will focus on these non-worst-case phenomena. It will explore probabilistic models of the input distribution, structured classes of inputs such as planted models, and empirical measurement of performance. The goal will be to provide tools best suited for the practical evaluation of algorithms.The workshop will enhance communication among the mathematics, computer science, statistics and operations research communities. It will be open to all potential participants, and the workshop findings (including video recordings of presentations) will be distributed to the public for comment and engagement. The organizers will encourage students to attend the workshop, and will actively recruit scientists from a diversity of backgrounds to contribute to a wide range of applications.

在计算复杂性理论中，当输入的大小趋于无穷大时，算法的性能通常由其最坏情况下的资源使用情况来定义。在实践中，这种渐近最坏情况度量可能不合适，原因如下：最坏情况性能可能只发生在从未在实践中发生的人为实例中；在实践中发生的实例可能具有特殊的结构特征；算法的平均情况性能可能比最坏情况要好得多；或者启发式算法可能会被经验观察到表现良好。研讨会将集中讨论这些非最坏情况的现象。它将探索输入分布的概率模型，输入的结构化类别，如种植模型，以及绩效的经验测量。我们的目标是提供最适合算法实际评估的工具。研讨会将加强数学、计算机科学、统计学和运筹学研究团体之间的交流。它将向所有潜在的参与者开放，研讨会的结果（包括演讲的视频记录）将分发给公众，以征求意见和参与。组织者将鼓励学生参加研讨会，并将积极招募来自不同背景的科学家，为广泛的应用做出贡献。