Javascript must be enabled

# Wai (Jenny) Law : Approximately Counting Perfect and General Matchings in Bipartite andGeneral Graphs

Approximating the permanent of a matrix with nonnegative entries is a well studied problem. The most successful approach to date uses Markov chains, and Jerrum, Sinclair, and Vigoda developed such a method that runs in polynomial time O(n^7 (log n)^4). We present a very different approach using self-reducible acceptance/rejection, and show that for a class of dense problems, our method has an O(n^4 log n) expected running time. Also, we extend our approach to approximate the number of perfect matchings in non-bipartite graphs and general matchings in general graphs.

**Category**: Graduate/Faculty Seminar**Duration**: 01:34:23**Date**: November 14, 2008 at 4:25 PM**Views**: 155-
**Tags:**seminar, Graduate/faculty Seminar

## 0 Comments