Abstract:
The complexity of many classical optimization problems and algorithms seems very well understood. However, very often theoretical results contradict observations made in practice. Many NP-hard optimization problems like the knapsack problem can be solved efficiently in practice and for many problems like linear programming algorithms with exponential worst-case running time outperform polynomial-time algorithms. The reason for this discrepancy is the pessimistic worst-case perspective adopted by theoreticians, in which the performance of an algorithm is solely measured by its behavior on the worst possible input. This does not take into consideration that worst-case inputs are often rather contrived and occur only rarely in practical applications. In order to provide a more realistic measure that can explain the practical performance of algorithms, Spielman and Teng introduced in 2001 the framework of smoothed analysis, in which the performance of an algorithm is measured on inputs that are subject to random noise. In this talk, we will present this framework and results on the smoothed analysis of the simplex method. Furthermore, we will use smoothed analysis to explain the practical success of local search heuristics for the traveling salesperson problem and for clustering problems.

References:
[1] David Arthur, Bodo Manthey, and Heiko Röglin. Smoothed analysis of the k-means method. Journal of the ACM, 58(5), 2011.
[2] Matthias Englert, Heiko Röglin, and Berthold Vöcking. Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP. In Proc. of 18th ACM-SIAM Symp. on Discrete Algorithms, pp. 1295-1304, 2007.
[3] Bodo Manthey and Heiko Röglin. Smoothed analysis: analysis of algorithms beyond worst case. it - Information Technology, 53(6):280-286, 2011.
[4] Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51(3): 385-463, 2004.
[5] Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Communications of the ACM, 52(1):76-84, 2009.
[6] Roman Vershynin. Beyond Hirsch conjecture: walks on random polytopes and smoothed complexity of the simplex method. SIAM Journal on Computing, 39(2):646-678, 2009.