Gurvits's doubly stochastic permanent inequality conjecture
Let be a doubly stochastic matrix, so that its entries are non-negative and every row and column sums to . The permanent is denoted by . Gurvits's permanent inequality conjecture. The following inequality holds:
If true, this inequality would imply a deterministic polynomial-time algorithm approximating the permanent of an non-negative matrix within relative factor . The source does not state that the inequality has been proved or disproved.
References
Primary source
M. Chertkov and A. B. Yedidia, “Approximating the Permanent with Fractional Belief Propagation”, arXiv:1108.0065 (2013).
Additional references
2 papers in this index state this conjecture (2011). The statement above is taken from the most recent of them; the others are arXiv:1107.4196.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.