Speaker: |
Manoj Gupta (Xerox Research Centre India Etamin Block 3, 4th Floor, Wing-A Prestige Technology Park II, Marathahalli - Sarajapur Outer Ring Road Bangalore 560103 ) |

Organiser: |
Kavitha Telikepalli |

Date: |
Thursday, 23 Jul 2015, 16:00 to 17:00 |

Venue: |
A-212 (STCS Seminar Room) |

(Scan to add to calendar)

Our results of maximum cardinality matching easily extend to maximum weighted matching. Using known schemes, we first obtain a $(3+\epsilon)$ approximation of maximum weighted matching with $O( \sqrt m \epsilon^{-2} \log N)$ update time. Using intricate rounding schemes, we then obtain a $(1+\epsilon)$ approximation of maximum matching in $O( \sqrt{m} \epsilon^{-2 - O(\epsilon^{-1})} \log N)$ update time. It is the first data-structure which maintains arbitrary quality approximation on a weighted graph.