Smoothed analysis of belief propagation and minimum-cost flow algorithms

Kamiel Cornelissen

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

91 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

Cornelissen, Kamiel. / Smoothed analysis of belief propagation and minimum-cost flow algorithms. Enschede : University of Twente, 2016. 114 p.
@phdthesis{15d602e285e04fe78269785d349c3a23,
title = "Smoothed analysis of belief propagation and minimum-cost flow algorithms",
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.",
keywords = "METIS-316699, IR-100450, Probabilistic Analysis, belief propagation algorithms, Smoothed Analysis, minimum-cost flow algorithms, EWI-27124, NWO 613.001.023",
author = "Kamiel Cornelissen",
note = "NWO 613.001.023",
year = "2016",
month = "5",
day = "27",
doi = "10.3990/1.9789036540971",
language = "Undefined",
isbn = "978-90-365-4097-1",
publisher = "University of Twente",
address = "Netherlands",
school = "University of Twente",

}

Smoothed analysis of belief propagation and minimum-cost flow algorithms. / Cornelissen, Kamiel.

Enschede : University of Twente, 2016. 114 p.

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

TY - THES

T1 - Smoothed analysis of belief propagation and minimum-cost flow algorithms

AU - Cornelissen, Kamiel

N1 - NWO 613.001.023

PY - 2016/5/27

Y1 - 2016/5/27

N2 - 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.

AB - 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.

KW - METIS-316699

KW - IR-100450

KW - Probabilistic Analysis

KW - belief propagation algorithms

KW - Smoothed Analysis

KW - minimum-cost flow algorithms

KW - EWI-27124

KW - NWO 613.001.023

U2 - 10.3990/1.9789036540971

DO - 10.3990/1.9789036540971

M3 - PhD Thesis - Research UT, graduation UT

SN - 978-90-365-4097-1

PB - University of Twente

CY - Enschede

ER -