An upper bound for permanents of nonnegative matrices

Details An upper bound for permanents of nonnegative matrices An upper bound for permanents of nonnegative matrices

2006-05-05

arxiv.org/abs/math/0605147v2

Mathematics

Combinatorics

Section 1.2 expanded

Scientific paper

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)}.

Affiliated with

Also associated with

No associations

Rating

An upper bound for permanents of nonnegative matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An upper bound for permanents of nonnegative matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An upper bound for permanents of nonnegative matrices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-607955