CaltechAUTHORS
  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) http://resolver.caltech.edu/CaltechCSTR:1996.cs-tr-96-17

[img]
Preview
Postscript - Submitted Version
See Usage Policy.

546Kb
[img]
Preview
PDF - Submitted Version
See Usage Policy.

450Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCSTR:1996.cs-tr-96-17

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.


Item Type:Report or Paper (Technical Report)
Additional Information:© 1996 California Institute of Technology. Supported by an NSF fellowship.
Group:Computer Science Technical Reports
Funders:
Funding AgencyGrant Number
NSF Graduate Research FellowshipUNSPECIFIED
Subject Keywords:Algorithms, combinatorial problems, permanent
Classification Code:AMS subject classifications 05,68
DOI:10.7907/Z9DN433K
Record Number:CaltechCSTR:1996.cs-tr-96-17
Persistent URL:http://resolver.caltech.edu/CaltechCSTR:1996.cs-tr-96-17
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
Collection:CaltechCSTR
Deposited By: Imported from CaltechCSTR
Deposited On:25 Apr 2001
Last Modified:11 Apr 2017 19:46

Repository Staff Only: item control page