Achievements and Prospects of Smoothed Analysis of Algorithms

There are many algorithms that work exceedingly well in practice but are known to perform poorly in the worst-case or lack good worst-case analyses. One of the most typical examples is the simplex method for linear programming. Spilman and Teng introduced the smoothed analyis of algorithms to explain the above contradiction successfully. The algorithm community pays close attention to smoothed analysis. Some concepts and the main achievements related to smoothed analysis are presented. The random perturbation model TSSP is proposed, which can overcome some limitations of the Partial Permutation model. The TSSP model is used in the smoothed analysis of algorithms like quick-sorting, whose performance is mainly determined by the initial order of the elements of an instance. A smoothed analysis of quick-sorting under the TSSP model is performed and the smoothed time complexity of quick-sorting is proved as O(2/λn×log\-2(n)), where λ is the random perturbation magnitude. Several prospects on smoothed analysis of algorithms are presented.