The permanent of a matrix is currently a well-studied combinatorial problem with applications in many fields, as it corresponds to the number of perfect matchings of a bipartite graph. For example in physics, computing the permanent is central to the study of the Dimer and Ising Models, although the exact computation of the permanent is intractable. Mathematicians began studying the permanent about two centuries ago, partly because of its superficial similarity to the determinant, which is a much easier problem.

Vigoda's breakthrough discovery is a randomized algorithm which approximates the permanent to within an arbitrarily close factor in time polynomial and in the size of the input. Therefore, with the use of randomness, arbitrarily good approximations can still be obtained. Vigoda's paper also introduces techniques that have already found several important computing, physics, and mathematical applications. The award was presented at the International Symposium on Mathematical Programming this month in Rio de Janeiro.

For more information about the Fulkerson Prize, visit http://www.ams.org/prizes/fulkerson-prize.html.

To view Vigoda's award-winning paper, visit http://www.cc.gatech.edu/~vigoda/Permanent.pdf.

Writer: Joy Weaks, College of Computing