Tailoring the Permanent Formula to Problem Instances
- Creators
- 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
Name | Size | Download all |
---|---|---|
md5:38117691e2d1eb053664c2f909670d51
|
460.9 kB | Preview Download |
md5:9c00b58fe7972a170fbe5b62ed8551db
|
559.7 kB | Download |
Additional details
- Eprint ID
- 26798
- Resolver ID
- CaltechCSTR:1996.cs-tr-96-17
- NSF Graduate Research Fellowship
- Created
-
2001-04-25Created from EPrint's datestamp field
- Updated
-
2019-10-03Created from EPrint's last_modified field
- Caltech groups
- Computer Science Technical Reports