Campus Event Calendar
Event Entry
New for: D1, D2, D3, D4
What and Who
Approximating permanents of complex matrices
Martin Fürer
Penn State University
AG1 Mittagsseminar
AG 1, AG 2, AG 3, AG 4
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 9 August 99
13:30
-- Not specified --
46.1
24
Saarbrücken
Abstract
A wide variety of algorithms for approximating permanents of
non-negative matrices have been proposed and analyzed before.
Usually, these approximation algorithms have been presented for
0-1 matrices, and it has been remarked that they extend to other
matrices as long as all entries are non-negative.
Here we present the first approximation algorithm for the
permanent of an arbitrary complex matrix. Like several other
approximation algorithms for the permanent, it is based on an
easily computable unbiased estimator. This is a random variable
whose expected value is equal to the permanent. The random
variable is computed by a randomized algorithm that mainly
consists of computing a determinant. After many repetitions, the
error is likely to be small compared to the sum of the absolute
values of the monomials.
non-negative matrices have been proposed and analyzed before.
Usually, these approximation algorithms have been presented for
0-1 matrices, and it has been remarked that they extend to other
matrices as long as all entries are non-negative.
Here we present the first approximation algorithm for the
permanent of an arbitrary complex matrix. Like several other
approximation algorithms for the permanent, it is based on an
easily computable unbiased estimator. This is a random variable
whose expected value is equal to the permanent. The random
variable is computed by a randomized algorithm that mainly
consists of computing a determinant. After many repetitions, the
error is likely to be small compared to the sum of the absolute
values of the monomials.
Contact
Roberto Solis-Oba
116
--email hidden
passcode not visible
logged in users only