Published January 2002
| public
Journal Article
A Permanent Algorithm with exp[Ω ((n^(1/3))/(2 ln n))] Expected Speedup for 0-1 Matrices
- Creators
- Bax, E.
- Franklin, J.
Chicago
An error occurred while generating the citation.
Abstract
This paper outlines a permanent algorithm with mildly exponential expected speedup over Ryser's inclusion and exclusion algorithm for 0-1 matrices. The algorithm is based on a finite-difference formula that is a generalization of Ryser's formula. The matrix is augmented by a column of entries selected to produce zero-valued terms in the formula. The algorithm achieves speedup by avoiding computation of many zero-valued terms.
Additional Information
© 2002 Springer. Received January 14, 1998; revised October 21, 1999. Communicated by A. Borodin. Online publication October 5, 2001. The first author thanks the second author for his guidance, insights, and example. We thank an anonymous referee for invaluable contributions to the development and presentation of these results.Additional details
- Eprint ID
- 101386
- Resolver ID
- CaltechAUTHORS:20200219-114918580
- Created
-
2020-02-19Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field