Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published April 25, 2001 | Submitted
Report Open

Tailoring the Permanent Formula to Problem Instances

Bax, Eric

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.

Additional Information

© 1996 California Institute of Technology. Supported by an NSF fellowship.

Attached Files

Submitted - postscript.pdf

Submitted - postscript.ps

Files

postscript.pdf
Files (1.0 MB)
Name Size Download all
md5:38117691e2d1eb053664c2f909670d51
460.9 kB Preview Download
md5:9c00b58fe7972a170fbe5b62ed8551db
559.7 kB Download

Additional details

Created:
August 20, 2023
Modified:
October 24, 2023