Quicklists
Javascript must be enabled

Wai (Jenny) Law : Approximately Counting Perfect and General Matchings in Bipartite andGeneral Graphs (Nov 14, 2008 4:25 PM)

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.

Add to Favorites

Please select playlist name from following

Create new playlist

Report Video

Please select the category that most closely reflects your concern about the video, so that we can review it and determine whether it violates our Community Guidelines or isn’t appropriate for all viewers. Abusing this feature is also a violation of the Community Guidelines, so don’t do it.

0 Comments

Comments Disabled For This Video