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

点击翻译按钮获取中文摘要

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.