Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PERMANENT, MONOMER-DIMER:
Reports tagged with permanent, monomer-dimer:
TR11-169 | 14th December 2011
Leonid Gurvits

#### Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation

Revisions: 2

Let $A \in \Omega_n$ be doubly-stochastic $n \times n$ matrix. Alexander Schrijver proved in 1998 the following remarkable inequality
\label{le}
per(\widetilde{A}) \geq \prod_{1 \leq i,j \leq n} (1- A(i,j)); \widetilde{A}(i,j) =: A(i,j)(1-A(i,j)), 1 \leq i,j \leq n

We prove in this paper the following generalization (or just clever ... more >>>

ISSN 1433-8092 | Imprint