Abstract
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.
Original language | English |
---|---|
Qualification | Doctor of Philosophy |
Awarding Institution |
|
Supervisors/Advisors |
|
Thesis sponsors | |
Award date | 27 May 2016 |
Place of Publication | Enschede |
Publisher | |
Print ISBNs | 978-90-365-4097-1 |
DOIs | |
Publication status | Published - 27 May 2016 |
Keywords
- METIS-316699
- IR-100450
- Probabilistic Analysis
- belief propagation algorithms
- Smoothed Analysis
- minimum-cost flow algorithms
- EWI-27124
- NWO 613.001.023