AF: Medium: Smoothed Analysis for Optimization and Games

许多在实践中工作得很好的算法和启发式算法在最坏情况分析下的性能很差，因为微妙的病理实例可能永远不会遇到，实际上，在理解这些算法方面造成了巨大的理论和实践差距。最著名的例子之一是线性规划的单纯形算法，它在实践中被广泛使用，但在最坏的情况下运行时间是指数的。为了对其成功提供一个更现实的解释，斯皮尔曼和邓丽君引入了平滑分析框架，该框架可以被视为经典最坏情况分析和平均情况分析的混合体。自那以后，平滑分析框架已被应用于数学规划、机器学习、数值分析等领域的一系列问题。其中，对算法的平滑分析以及组合优化和算法博弈论中出现的问题在过去十年中得到了深入的研究。然而，尽管取得了很大进展，但一些最基本的问题仍然悬而未决，目前可用于执行平滑分析的工具仍然有限。这个项目计划探索在优化和博弈论问题的算法平滑分析中出现的一些新的方向和具有挑战性的问题。该项目的目标是开发新的技术，通过平滑分析的镜头，使人们能够更好地理解广泛的算法和问题。研究团队正在广泛传播该项目的新成果，方法是在跨学科会议、主要大学和研究实验室发表演讲，并开发关于平滑分析的新高级课程。该项目的跨学科性质可能会吸引不同背景的学生。除了为博士生提供建议和指导外，研究团队还积极地让本科生参与到可接触到的研究项目中。研究团队还参与了可能有助于培养更广泛人群对计算机科学的兴趣的外展活动。为了顺利分析组合优化问题，研究团队将重点放在局部搜索范式上。该团队计划研究的一个核心问题是局部最大约束满足问题的翻转算法的平滑复杂性，包括Max-Cut和Max-3SAT等例子。该团队还计划研究旅行商问题(TSP)的启发式算法的平滑复杂性，如k-opt。对k-opt的更好的理解可能会为Lin-Kernighan的平滑分析带来新的曙光，Lin-Kernighan是在实践中应用最广泛的TSP启发式算法之一。为了对博弈论和经济学中的算法和问题进行平滑分析，该团队致力于研究求解马尔可夫决策过程以及更一般的随机博弈的策略和值迭代的平滑复杂性。该团队还致力于为双矩阵博弈的Lemke-Howson算法和市场均衡的全局牛顿方法的平滑复杂性建立无条件的下限。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Many algorithms and heuristics that work well in practice have poor performance under the worst-case analysis due to delicate pathological instances that one may never encounter, practically speaking, creating a huge theory-practice gap in the understanding of such algorithms. One of the best known such examples is the Simplex algorithm for Linear Programming, which is widely used in practice but has exponential running time in the worst case. To provide a more realistic explanation for its success, Spielman and Teng introduced the smoothed-analysis framework, which can be viewed as a hybrid of the classical worst-case and average-case analysis. The smoothed-analysis framework has since been applied to a range of problems in areas such as mathematical programming, machine learning, numerical analysis, etc. Among them, the smoothed analysis of algorithms and problems that arise from combinatorial optimization and algorithmic game theory has been studied intensively during the past decade. However, despite much progress, some of the most fundamental problems remain wide open, and tools currently available for performing smoothed analysis remain limited. This project plans to explore some of the new directions and challenging problems that have emerged in the smoothed analysis of algorithms for optimization and game-theoretic problems. The goal of the project is to develop new techniques that will enable better understanding of a broad range of algorithms and problems through the lens of smoothed analysis. The research team is broadly disseminating new results from the project by giving talks at interdisciplinary conferences, major universities and research labs, and by developing new advanced courses on smoothed analysis. The interdisciplinary nature of the project is likely to appeal to students with diverse backgrounds. In addition to advising and mentoring Ph.D. students, the research team is actively involving undergraduate students in accessible research projects. The research team is also participating in outreach activities that may help develop interest in Computer Science from a broader population.For the smoothed analysis of combinatorial-optimization problems, the research team is focusing on the local-search paradigm. A core problem that the team plans to study is the smoothed complexity of the FLIP algorithm for Local Maximum Constraint Satisfaction problems, including examples such as MAX-CUT and MAX-3SAT. The team also plans to study the smoothed complexity of heuristics for the Traveling Salesman Problem (TSP), such as k-Opt. Improved understanding of k-Opt may shed new light on the smoothed analysis of Lin-Kernighan, one of the most widely used heuristics for TSP in practice. For the smoothed analysis of algorithms and problems from game theory and economics, the team is working to investigate the smoothed complexity of Policy and Value Iteration for solving Markov decision processes and more generally, stochastic games. The team is also working to establish unconditional lower bounds for the smoothed complexity of the Lemke-Howson algorithm for bimatrix games and the global Newton method of Smale for market equilibria.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.