|M. Pawan Kumar|
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.
Topic 1: Combinatorial Approach [PPT] [PDF]