A Caltech Library Service

Tailoring the Permanent Formula to Problem Instances

Bax, Eric (1996) Tailoring the Permanent Formula to Problem Instances. California Institute of Technology , Pasadena, CA. (Unpublished)

Postscript - Submitted Version
See Usage Policy.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Report or Paper (Technical Report)
Additional Information:© 1996 California Institute of Technology. Supported by an NSF fellowship.
Group:Computer Science Technical Reports
Funding AgencyGrant Number
NSF Graduate Research FellowshipUNSPECIFIED
Subject Keywords:Algorithms, combinatorial problems, permanent
Classification Code:AMS subject classifications 05,68
Record Number:CaltechCSTR:1996.cs-tr-96-17
Persistent URL:
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26798
Deposited By: Imported from CaltechCSTR
Deposited On:25 Apr 2001
Last Modified:03 Oct 2019 03:18

Repository Staff Only: item control page