Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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
\begin{equation} \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
\end{equation}
We prove in this paper the following generalization (or just clever ... more >>>




ISSN 1433-8092 | Imprint