*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Dani Denton
denton at cc dot gatech dot edu
Summary Sentence: Seth Pettie presents a talk as part of the ARC Colloquium series.
Full Summary: No summary paragraph submitted.
Seth Pettie(Refreshments will be served in Klaus 2222 at 2 pm)
Title:
Weighted Matching on General Graphs: Faster and Simpler
Abstract :
We present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs. The algorithm runs in O(mn^{1/2}log(nW)) time, where m, n, and W are the numbers of edges, vertices and maximum integer edge weight. This bound matches the fastest algorithm for bipartite graphs and comes within a log(nW) factor of the Micali-Vazirani cardinality matching algorithm. In terms of running time our algorithm is just slightly faster than the previous best (Gabow and Tarjan, 1991) by a roughly (log n)^{1/2} factor. However, it is dramatically simpler to describe and analyze.
Joint work with Ran Duan (IIIS, Tsinghua) and Hsin-Hao Su (University of Michigan). Manuscript available at http://arxiv.org/abs/1411.1919v2.
Bio:
Seth Pettie received his Ph.D. in Computer Science from the University of Texas at Austin, in 2003. From 2003-2006 he was an Alexander von Humboldt Postdoctoral Fellow at the Max Planck Institute for Computer Science, in Saarbruecken, Germany. Since 2006 he has been a professor of Electrical Engineering and Computer Science at the University of Michigan, in Ann Arbor.
Seth Pettie, Assoc. Prof. in Computer Science and Engineering University of Michigan, Ann Arbor http://web.eecs.umich.edu/~pettie
