An upper bound for permanents of nonnegative matrices
| dc.creator | Samorodnitsky, Alex | |
| dc.date | 2006-05-05 | |
| dc.date | 2006-07-23 | |
| dc.date.accessioned | 2026-07-07T07:13:57Z | |
| dc.date.available | 2026-07-07T07:13:57Z | |
| dc.description | 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\times n matrix within exp{n - O(n/\log n)}. | |
| dc.description | Section 1.2 expanded | |
| dc.identifier | https://arxiv.org/abs/math/0605147 | |
| dc.identifier | http://arxiv.org/abs/math/0605147 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/112673 | |
| dc.subject | Combinatorics | |
| dc.title | An upper bound for permanents of nonnegative matrices | |
| dc.type | text |