An upper bound for permanents of nonnegative matrices
From MaRDI portal
Publication:2474496
Abstract: A recent conjecture of Caputo, Carlen, Lieb, and Loss, and, independently, of the author, states that the maximum of the permanent of a matrix whose rows are unit vectors in l_p is attained either for the identity matrix I or for a constant multiple of the all-1 matrix J. The conjecture is known to be true for p = 1 (I) and for p ge 2 (J). We prove the conjecture for a subinterval of (1,2), and show the conjectured upper bound to be true within a subexponential factor (in the dimension) for all 1 < p < 2. In fact, for p bounded away from 1, the conjectured upper bound is true within a constant factor. This leads to a mild (subexponential) improvement in deterministic approximation factor for the permanent. We present an efficient deterministic algorithm that approximates the permanent of a nonnegative n imes n matrix within exp{n - O(n/log n)}.
Recommendations
Cites work
- scientific article; zbMATH DE number 3458807 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 1149836 (Why is no real title available?)
- A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains
- A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
- A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
- A short proof of Minc's conjecture
- A study of the van der Waerden conjecture and its generalizations
- An entropy proof of Bregman's theorem
- An inequality of Hadamard type for permanents
- Hyperbolic polynomials approach to van der Waerden/Schrijver-Valiant like conjectures, sharper bounds, simpler proofs and algorithmic applications
- New permanental upper bounds for nonnegative matrices
- Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
- The solution of van der Waerden's problem for permanents
Cited in
(16)- Permanental bounds for the signless Laplacian matrix of a unicyclic graph with diameter \(d\)
- Permanental bounds for nonnegative matrices via decomposition
- A remark on approximating permanents of positive definite matrices
- A note on a conjecture on permanents
- Counterexample to a conjecture of mehta regarding permanental maximization
- Permanental bounds for the signless Laplacian matrix of bipartite graphs and unicyclic graphs
- On the boundary of totally positive upper triangular matrices
- An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs
- An Upper Bound for the Permanent of a 3-Dimensional (0, 1)-Matrix
- New permanental upper bounds for nonnegative matrices
- New permanental bounds for Ferrers matrices
- Some upper bounds for permanents of (0, 1)-matrices
- Permanental dominance of the normalized single-hook immanants on the positive semi-definite matrices
- A note on some upper bounds for permanents of (0, 1)-matrices
- Permanental bounds of the Laplacian matrix of trees with given domination number
- \(p\)-adic matrix valued inequalities
This page was built for publication: An upper bound for permanents of nonnegative matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2474496)
