ACO Special Seminar: Vijay V. Vazirani, Georgia Tech

Event Details
  • Date/Time:
    • Monday February 25, 2013
      3:30 pm
  • Location: Klaus Classroom 2447
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact

denton@cc.gatech.edu

Summaries

Summary Sentence: No summary sentence submitted.

Full Summary: No summary paragraph submitted.

Media
  • vaziranix vaziranix
    (image/jpeg)

Abstract:
For all practical purposes, the Micali-Vazirani algorithm, discovered in 1980, is still the most efficient known maximum matching algorithm (for very dense graphs, slight asymptotic improvement can be obtained using fast matrix multiplication). However, this has remained a "black box" result for the last 32 years. We hope to change this with the help of a recent paper giving a simpler proof and exposition of the algorithm:  http://arxiv.org/abs/1210.4594

In the interest of covering all the ideas, we will assume that the audience is familiar with basic notions such as augmenting paths and bipartite matching algorithm.

Additional Information

In Campus Calendar
Yes
Groups

College of Computing, School of Computer Science

Invited Audience
No audiences were selected.
Categories
No categories were selected.
Keywords
No keywords were submitted.
Status
  • Created By: Dani Denton
  • Workflow Status: Draft
  • Created On: Feb 21, 2013 - 6:31am
  • Last Updated: Oct 7, 2016 - 10:02pm