ARC Colloquium: Seth Pettie–University of Michigan

Event Details
Contact

Dani Denton
denton at cc dot gatech dot edu

Summaries

Summary Sentence: Seth Pettie presents a talk as part of the ARC Colloquium series.

Full Summary: No summary paragraph submitted.

Media
  • Seth Pettie Seth Pettie
    (image/jpeg)

(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


Related Links

Additional Information

In Campus Calendar
No
Groups

College of Computing, School of Computer Science, ARC

Invited Audience
Undergraduate students, Faculty/Staff, Public, Graduate students
Categories
Seminar/Lecture/Colloquium
Keywords
Algorithm and Randomness Center, ARC, ARC Colloquium, Seth Pettie
Status
  • Created By: Josie Giles
  • Workflow Status: Published
  • Created On: Nov 26, 2014 - 9:43am
  • Last Updated: Apr 13, 2017 - 5:21pm