Smoothed analysis of belief propagation and minimum-cost flow algorithms

Algorithms that have good worst-case performance are not always the ones that perform best in practice. The smoothed analysis framework is a way of analyzing algorithms that usually matches practical performance of these algorithms much better than worst-case analysis. In this thesis we apply smoothed analysis to two classes of algorithms: minimum-cost flow algorithms and belief propagation algorithms. The minimum-cost flow problem is the problem of sending a prescribed amount of flow through a network in the cheapest possible way. It is very well known, and over the last half a century many algorithms have been developed to solve it. We analyze three of these algorithms (the successive shortest path algorithm, the minimum-mean cycle canceling algorithm, and the network simplex algorithm) in the framework of smoothed analysis and show lower and upper bounds on their smoothed running-times. The belief propagation algorithm is a message-passing algorithm for solving probabilistic inference problems. Because of its simplicity, it is very popular in practice. However, its theoretical behavior is not well understood. To obtain a better theoretical understanding of the belief propagation algorithm, we apply it to several well-studied optimization problems. We analyze under which conditions the belief propagation algorithm converges to the correct solution and we analyze its smoothed running-time.