{"51703":{"#nid":"51703","#data":{"type":"news","title":"Vigoda Wins Renowned Fulkerson Prize","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003E(August 16, 2006)--\u003C\/strong\u003ECollege of Computing Associate Professor Eric Vigoda recently won the 2006 Delbert Ray Fulkerson Prize for his paper titled \u201cA polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries,\u201d co-authored with Mark Jerrum at the University of Edinburgh and Alistair Sinclair at UC Berkeley. The \u0022Fulkerson Prize\u0022 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 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.\u003C\/p\u003E\n\u003Cp\u003EThe 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.\u003C\/p\u003E\n\u003Cp\u003EVigoda\u0027s breakthrough discovery is a randomized algorithm which approximates the permanent to within an arbitrarily close factor in time polynomial in the size of the input. Therefore, with the use of randomness, arbitrarily good approximations can still be obtained. Vigoda\u2019s 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.\u003C\/p\u003E\n\u003Cp\u003EFor more information about the Fulkerson Prize,\u00a0\u003Ca href=\u0022http:\/\/www.ams.org\/prizes\/fulkerson-prize.html\u0022 target=\u0022_blank\u0022\u003Eclick here\u003C\/a\u003E.\u003C\/p\u003E\n\u003Cp\u003ETo view Eric Vigoda\u2019s award-winning paper,\u00a0\u003Ca href=\u0022http:\/\/www.cc.gatech.edu\/~vigoda\/Permanent.pdf\u0022 target=\u0022_blank\u0022\u003Eclick here\u003C\/a\u003E.\u00a0\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003ECollege of Computing Associate Professor Eric Vigoda\u00a0recently won the 2006 Delbert Ray Fulkerson Prize, a prestigious award given every three years for breakthrough discoveries in Discrete Mathematics.\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":"","uid":"27154","created_gmt":"2010-02-09 21:46:52","changed_gmt":"2016-10-08 03:05:12","author":"Louise Russo","boilerplate_text":"","field_publication":"","field_article_url":"","dateline":{"date":"2006-08-16T00:00:00-04:00","iso_date":"2006-08-16T00:00:00-04:00","tz":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}