Smoothed analysis of belief propagation and minimum-cost flow algorithms

Kamiel Cornelissen

Research output: ThesisPhD Thesis - Research UT, graduation UT

223 Downloads (Pure)

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 languageUndefined
Awarding Institution
  • University of Twente
Supervisors/Advisors
  • Uetz, Marc Jochen, Supervisor
  • Manthey, Bodo, Advisor
Thesis sponsors
Award date27 May 2016
Place of PublicationEnschede
Publisher
Print ISBNs978-90-365-4097-1
DOIs
Publication statusPublished - 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

Cite this