Approximating the permanent of a matrix with nonnegative entries

03/30/2010 - 12:15pm
03/30/2010 - 1:10pm
Mark Huber (Claremont McKenna College)

Finding the determinant of a matrix is made easy by taking advantage of invariants arising from its geometric nature. The permanent slightly tweaks the formula for the determinant, but changes it into a combinatorial entity, making calculation far more difficult. Finding the permanent of a matrix, even when all the entries of the matrix are 0 or 1, is a #P complete problem. Still, all is not lost, as there are upper bounds like Minc's inequality, and lower bounds like Van der Waerden's Inequality. I will show how these two inequalities can be effectively used to construct a Monte Carlo algorithm for approximating the permanent. The permanent is related to counting perfect matchings in a bipartite graph, and this algorithm gives the first method for exact uniform simulation of perfect matchings for a nontrivial class of bipartite graphs.

Millikan 208 (Pomona College)