Approximate Computation
When the entries of A are nonnegative, the permanent can be computed approximately in probabilistic polynomial time, up to an error of εM, where M is the value of the permanent and ε > 0 is arbitrary. In other words, there exists a fully polynomial-time randomized approximation scheme (FPRAS) (Jerrum, Vigoda & Sinclair (2001)).
The most difficult step in the computation is the construction of an algorithm to sample almost uniformly from the set of all perfect matchings in a given bipartite graph: in other words, a fully polynomial almost uniform sampler (FPAUS). This can be done using a Markov chain Monte Carlo algorithm that uses a Metropolis rule to define and run a Markov chain whose distribution is close to uniform, and whose mixing time is polynomial.
It is possible to approximately count the number of perfect matchings in a graph via the self-reducibility of the permanent, by using the FPAUS in combination with a well-known reduction from sampling to counting due to Jerrum, Valiant & Vazirani (1986). Let denote the number of perfect matchings in . Roughly, for any particular edge in, by sampling many matchings in and counting how many of them are matchings in, one can obtain an estimate of the ratio . The number is then, where can be approximated by applying the same method recursively.
Read more about this topic: Computing The Permanent
Famous quotes containing the words approximate and/or computation:
“A worker may be the hammers master, but the hammer still prevails. A tool knows exactly how it is meant to be handled, while the user of the tool can only have an approximate idea.”
—Milan Kundera (b. 1929)
“I suppose that Paderewski can play superbly, if not quite at his best, while his thoughts wander to the other end of the world, or possibly busy themselves with a computation of the receipts as he gazes out across the auditorium. I know a great actor, a master technician, can let his thoughts play truant from the scene ...”
—Minnie Maddern Fiske (18651932)