Polytopes, permanents and graphs with large factors

P Dagum, M Luby, M Mihail, U Vazirani - [Proceedings 1988] 29th …, 1988 - computer.org
P Dagum, M Luby, M Mihail, U Vazirani
[Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science, 1988computer.org
Randomized algorithms for approximating the number of perfect matchings in a graph are
considered. An algorithm that is a natural simplification of one suggested and analyzed
previously is introduced and analyzed. One of the key ideas is to view the analysis from a
geometric perspective: it is proved that for any graph G the k-slice of the well-known
Edmonds matching polytope has magnification 1. For a bipartite graph G=(U, V, E), mod U
mod= mod V mod= n, with d edge-disjoint perfect matchings, it is proved that the ratio of the …
Abstract
Randomized algorithms for approximating the number of perfect matchings in a graph are considered. An algorithm that is a natural simplification of one suggested and analyzed previously is introduced and analyzed. One of the key ideas is to view the analysis from a geometric perspective: it is proved that for any graph G the k-slice of the well-known Edmonds matching polytope has magnification 1. For a bipartite graph G=(U, V, E), mod U mod= mod V mod= n, with d edge-disjoint perfect matchings, it is proved that the ratio of the number of almost perfect matchings to the number of perfect matchings is at most n/sup 3n/d/. For any constant alpha> 0 this yields aa fully polynomial randomized algorithm for approximating the number of perfect matchings in bipartite graphs with d> or= alpha n. Moreover, for some constant c> 0 it is the fastest known approximation algorithm for bipartite graphs with d> or= clog n.
computer.org