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

[img]
Preview
Postscript
See Usage Policy.

546Kb
[img]
Preview
Other (Adobe PDF (461KB))
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)
Group:Computer Science Technical Reports
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:26 Dec 2012 14:05

Repository Staff Only: item control page