An upper bound for permanents of nonnegative matrices
From MaRDI portal
Publication:2474496
DOI10.1016/J.JCTA.2007.05.010zbMATH Open1165.15008arXivmath/0605147OpenAlexW2045175541MaRDI QIDQ2474496FDOQ2474496
Authors: Alex Samorodnitsky 
Publication date: 6 March 2008
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
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)}.
Full work available at URL: https://arxiv.org/abs/math/0605147
Recommendations
Determinants, permanents, traces, other special matrix functions (15A15) Miscellaneous inequalities involving matrices (15A45)
Cites Work
- Title not available (Why is that?)
- A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains
- Title not available (Why is that?)
- An entropy proof of Bregman's theorem
- A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
- Title not available (Why is that?)
- An inequality of Hadamard type for permanents
- Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
- A short proof of Minc's conjecture
- The solution of van der Waerden's problem 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
- A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
- A study of the van der Waerden conjecture and its generalizations
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 Upper Bound for the Permanent of a 3-Dimensional (0, 1)-Matrix
- An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs
- New permanental upper bounds for nonnegative matrices
- Some upper bounds for permanents of (0, 1)-matrices
- New permanental bounds for Ferrers 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)
