New permanental upper bounds for nonnegative matrices

Abstract

Using a simple concavity argument together with the scale-symmetries of the permanent function, we derive a handful of upper bounds for the permanent of a nonnegative matrix. Each is better than our previously best upper bound, and agrees with the Minc-Brègman bound when applied to a (0,1)-matrix. We show how sharpening, a different application of scale-symmetries, can be used to improve upon virtually any extant permanental upper or lower bound for nonnegative matrices. Indeed, when applied to a (0,1)-matrix, the sharpened versions of the new upper bounds typically improve, sometimes considerably, upon the Minc-Brègman bound itself. We also indicate how our methods apply to lower bounds.