Abstract:
In this talk, we will give an overview of known results about smoothed analysis. In particular, we will use smoothed analysis to study the complexity of binary optimization problems and give an explanation why the knapsack problem is easy to solve in practice.
The analysis of the knapsack problems turns out to be related to the analysis of multi-criteria optimization problems. A well-established heuristic approach for solving such problems is to enumerate the set of Pareto-optimal solutions. The heuristics following this principle are often successful in practice. Their running time, however, depends on the number of enumerated solutions, which can be exponential in the worst case. To explain their success in practice, we show that in expectation the number of Pareto-optimal solutions is polynomial if inputs are subject to random noise.

References:
[1] Rene Beier, Heiko Röglin, and Berthold Vöcking. The smoothed number of pareto optimal solutions in bicriteria integer optimization. In Proc. of the 12th Conference on Integer Programming and Combinatorial Optimization, pp. 53-67, 2007.
[2] Rene Beier and Berthold Vöcking. Random knapsack in expected polynomial time. Journal of Computer and System Sciences 69(3): 306-329 (2004)
[3] Rene Beier and Berthold Vöcking. Typical properties of winners and losers in discrete optimization. SIAM Journal on Computing 35(4): 855-881 (2006)
[4] Tobias Brunsch and Heiko Röglin. Improved smoothed analysis of multiobjective optimization. In Proc. of the 44th ACM Symposium on Theory of Computing, pp. 407-426, 2012.
[5] Bodo Manthey and Heiko Röglin. Smoothed analysis: analysis of algorithms beyond worst case. it - Information Technology, 53(6):280-286, 2011.
[6] 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.