Totally Unimodular Matrices in Linear Programming - Nate Veldt

NOTE: My apologies for the fuzzy picture in the first minute. The picture does stabilize and is clear from the 0:50 point on. Nate Veldt, Purdue University Math department PUNLAG is a student-led seminar in numerical linear algebra at Purdue University. Abstract: Integer linear programming is an NP-complete problem in general, but under certain assumptions an ordinary linear program will automatically yield an integral solution. In this talk we will introduce totally unimodular matrices and prove that linear programs with a totally unimodular constraint matrix will have an integral solution vector. We will apply this theorem by considering a few standard graph algorithms that can be expressed as a linear program with totally unimodular constraints.