Tata Institute of Fundamental Research
Fully Dynamic $(1+\epsilon)$-Approximate Matchings
STCS Seminar
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)
Abstract:
Abstract : We study data structures that maintain approximate maximum matchings in graphs under edge insertions/deletions. Our main result is a data structure that maintains a matching whose size is at least $(1 - \epsilon)$ of the maximum in worst case $O(\sqrt{m}\epsilon^{-2})$ per update. It is the first data structure that is able to maintain arbitrary quality approximations on sparse graphs in sublinear time per update.
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.
| 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)
Abstract:
Abstract : We study data structures that maintain approximate maximum matchings in graphs under edge insertions/deletions. Our main result is a data structure that maintains a matching whose size is at least $(1 - \epsilon)$ of the maximum in worst case $O(\sqrt{m}\epsilon^{-2})$ per update. It is the first data structure that is able to maintain arbitrary quality approximations on sparse graphs in sublinear time per update.
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.
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.