CS251 Lecture Notes - Joseph Fourier, Weak Duality, Disjoint Sets
12 Dec 2012
School
Department
Course
Professor
Document Summary
In this chapter we will consider two classical optimization problems, namely the problem of. Nding a shortest path between a xed pair of vertices in an undirected graph and the the prob- lem of nding a minimum cost perfect matching in a bipartite graph. These two optimization problems were introduced in chapter 1. We will present ef cient algorithms for both these problems and show in the process that the natural framework for understanding these prob- lems is the theory of linear programming duality. A note to the reader, section a. 1 on shortest paths, and section a. 2 on minimum cost perfect matchings are independent and introduce the same basic concepts of duality theory. Moreover, the material in these sections is not essential for the remainder of the book. Hence, it is possible for the reader to focus on one of these two sections only. Recall the shortest path problem from chapter 1.
