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

计算机科学家们一直面临着一个挑战，即存在一些在实践中运行良好的卓越算法，但这些算法的理论分析表明，这些算法应该表现不佳或不确定。 这一问题的根源在于传统的理论分析是在算法的最坏输入下衡量算法的性能。 本研究使用平滑分析来分析算法的性能，平滑分析是一种新的算法性能度量，可以更好地预测实际性能。 使用平滑分析，这项研究的目的是解释一些算法的良好的实际性能，是著名的优于悲观的最坏情况分析。 特别是，算法，采取真实的或复杂的输入，如那些通常发生在科学和工程应用，检查随机扰动下的最坏情况input.The最有名的，单纯形法线性规划，是该文件的主题介绍平滑分析。 然而，这项工作只研究了一个很少使用的主元规则。 本研究尝试在更常用的主元规则下对单纯形法进行平滑分析。 它还考虑光滑分析的邻域点方法和算法的凸规划。 一种尝试是将这种分析扩展到采用离散输入的算法。

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.