Tailoring the Permanent Formula to Problem Instances

Abstract

A parameterized set of finite difference formulas have been developed for the permanent. One parameter setting produces Ryser's [2] inclusion and exclusion formula. Other parameter settings yield formulas that can be computed more efficiently. One group of settings introduces symmetry, so only half the terms need to be computed. Some of these settings produce formulas that have many zero-valued terms when applied to matrices drawn from random distributions. Gathering the zero-valued terms and removing them from the computation substantially reduces the time required to compute the permanent [1]. This paper explores methods to tailor the parameter settings to specific matrices, choosing the formula based on the problem instance to increase the number of zero-valued terms.