M. Pawan Kumar 
HOME

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 stcut of a directed graph. We will formulate it as a discrete optimization problem, and show its equivalence to the maximum stflow problem. This equivalence relationship will allow us to discuss some of the most commonly used efficient algorithms for solving the minimum stcut 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 stflow problem as a linear program. This will allow us to derive its dual, which we will show to be equivalent to the minimum stcut problem.
Topic 1: Combinatorial Approach [PPT] [PDF] 