M. Pawan Kumar
 
 

HOME

RESEARCH

PUBLICATIONS

GROUP

TALKS

TEACHING

CV

 

 

 

 

 

 

GRAPH CUTS AND LINEAR PROGRAMMING FOR ENERGY MINIMIZATION

M. Pawan Kumar

Summer School, Institute for Informatics, University of Zurich, 2016

The course consists of three parts. In the first part, we will consider the classical combinatorial optimization problem of finding the minmum st-cut of a directed graph. We will formulate it as a discrete optimization problem, and show its equivalence to the maximum st-flow problem. This equivalence relationship will allow us to discuss some of the most commonly used efficient algorithms for solving the minimum st-cut problem. In the second part, we will illustrate how linear programming can be used as a practical tool to solve discrete optimization problems. To this end, we will begin by formulating the maximum st-flow problem as a linear program. This will allow us to derive its dual, which we will show to be equivalent to the minimum st-cut problem.
The final part of the course will consider the problem of energy minimization in undirected graphical models (Markov random fields, Conditional random fields). As the problem is known to be NP-hard, we can only hope to obtain an approximate solution. We will show how to build practical approximate algorithms with the aid of the efficient algorithms for the minimum st-cut problem. The algorithms are not only very fast in practice, but also come with strong theoretical guarantees on the quality of the solution. We will connect the guarantees of minimum st-cut based methods with the more traditional linear programming based approaches.

Topic 1: Combinatorial Approach  [PPT]   [PDF]

Topic 2, Part 1: Linear Programming  [PPT]   [PDF]

Topic 2, Part 2: Integer Linear Programming  [PPT]   [PDF]

Topic 2, Part 3: Max-Flow as Linear Programming  [PPT]   [PDF]

Topic 3: Metric Labeling  [PPT]   [PDF]