ITR/SY(CISE): Why algorithms work well in practice: pertubation-based average-case analysis of the simplex algorithm and beyond

ITR/SY(CISE)：为什么算法在实践中表现良好：单纯形算法及其他算法的基于扰动的平均情况分析

• 批准号: 0112487
• 负责人: Daniel Spielman
• 金额: $ 27.2万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-08-01 至 2004-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0112487&HistoricalAwards=false
• 关键词: ITR; SY; CISE; Why; algorithms

Computer Scientists have been challenged by the existence ofremarkable algorithms that work well in practice, but whosetheoretical analyses suggest that these algorithms should performpoorly or are inconclusive. The root of this problem is thattraditional theoretical analyses measure the performance ofalgorithms on their worst inputs. This research analyzes theperformance of algorithms using smoothed analysis, a new measure ofthe performance of algorithms that can better predict practicalperformance. Using smoothed analysis, this research aims to explainthe good practical performance of some algorithms that are famousfor outperforming pessimistic worst-case analyses. In particular, algorithms that take real or complex inputs, such asthose that usually occur in scientific and engineering applications,are examined under random perturbations of their worst-case inputs.The most famous of these, the simplex method for linear programming,was the subject of the paper introducing smoothed analysis. Yet, thiswork only investigated one rarely-used pivot rule. This researchattempts smoothed analyses of the simplex method under more commonlyused pivot rules. It also considers smoothed analyses of interiorpoint methods and algorithms for convex programming. An attempt isbeing made to extend this analysis to algorithms that take discreteinputs.

计算机科学家受到了挑战，因为存在着在实践中工作得很好的非凡算法，但理论分析表明，这些算法应该表现不佳或没有定论。这个问题的根源在于，传统的理论分析是衡量算法在最差输入时的性能。这项研究使用平滑分析来分析算法的性能，这是一种新的算法性能衡量标准，可以更好地预测实际性能。使用平滑分析，本研究旨在解释一些以优于悲观最坏情况分析而闻名的算法的良好实用性能。特别是，采用实数或复数输入的算法，例如那些在科学和工程应用中经常出现的算法，在其最坏输入的随机扰动下被检查。其中最著名的线性规划的单纯形法是引入平滑分析的论文的主题。然而，这项工作只调查了一个很少使用的枢轴规则。本研究尝试在更常用的枢轴规则下对单纯形法进行平滑分析。它还考虑了凸规划的内点方法和算法的光滑分析。有人试图将这一分析扩展到采用离散输入的算法。