Abstract
Original language  Undefined 

Awarding Institution 

Supervisors/Advisors 

Thesis sponsors  
Award date  27 May 2016 
Place of Publication  Enschede 
Publisher  
Print ISBNs  9789036540971 
DOIs  
Publication status  Published  27 May 2016 
Keywords
 METIS316699
 IR100450
 Probabilistic Analysis
 belief propagation algorithms
 Smoothed Analysis
 minimumcost flow algorithms
 EWI27124
 NWO 613.001.023
Cite this
}
Smoothed analysis of belief propagation and minimumcost flow algorithms. / Cornelissen, Kamiel.
Enschede : University of Twente, 2016. 114 p.Research output: Thesis › PhD Thesis  Research UT, graduation UT
TY  THES
T1  Smoothed analysis of belief propagation and minimumcost flow algorithms
AU  Cornelissen, Kamiel
N1  NWO 613.001.023
PY  2016/5/27
Y1  2016/5/27
N2  Algorithms that have good worstcase 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 worstcase analysis. In this thesis we apply smoothed analysis to two classes of algorithms: minimumcost flow algorithms and belief propagation algorithms. The minimumcost 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 minimummean cycle canceling algorithm, and the network simplex algorithm) in the framework of smoothed analysis and show lower and upper bounds on their smoothed runningtimes. The belief propagation algorithm is a messagepassing 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 wellstudied optimization problems. We analyze under which conditions the belief propagation algorithm converges to the correct solution and we analyze its smoothed runningtime.
AB  Algorithms that have good worstcase 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 worstcase analysis. In this thesis we apply smoothed analysis to two classes of algorithms: minimumcost flow algorithms and belief propagation algorithms. The minimumcost 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 minimummean cycle canceling algorithm, and the network simplex algorithm) in the framework of smoothed analysis and show lower and upper bounds on their smoothed runningtimes. The belief propagation algorithm is a messagepassing 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 wellstudied optimization problems. We analyze under which conditions the belief propagation algorithm converges to the correct solution and we analyze its smoothed runningtime.
KW  METIS316699
KW  IR100450
KW  Probabilistic Analysis
KW  belief propagation algorithms
KW  Smoothed Analysis
KW  minimumcost flow algorithms
KW  EWI27124
KW  NWO 613.001.023
U2  10.3990/1.9789036540971
DO  10.3990/1.9789036540971
M3  PhD Thesis  Research UT, graduation UT
SN  9789036540971
PB  University of Twente
CY  Enschede
ER 