College of Computing associate professor Eric Vigoda recently won the 2006 Delbert Ray Fulkerson Prize for his paper titled "A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries," co-authored with Mark Jerrum at the University of Edinburgh and Alistair Sinclair at UC Berkeley. The "Fulkerson Prize" is a prestigious award given every three years for outstanding papers in the area of Discrete Mathematics, and is sponsored jointly by the Mathematical Programming Society and the American Mathematical Society. Vigoda is the first from the College of Computing at Georgia Tech to win this celebrated prize, although past Georgia Tech winners include Arkadi Nemirovski (1982) from the School of Industrial and Systems Engineering and Robin Thomas (1994) from the School of Mathematics.

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