BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Computer Science and Engineering - ECPv6.13.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Computer Science and Engineering
X-ORIGINAL-URL:https://homecse.iitd.ac.in
X-WR-CALDESC:Events for Computer Science and Engineering
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Kolkata
BEGIN:STANDARD
TZOFFSETFROM:+0530
TZOFFSETTO:+0530
TZNAME:IST
DTSTART:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Kolkata:20250120T143000
DTEND;TZID=Asia/Kolkata:20250120T163000
DTSTAMP:20260924T080057
CREATED:20241212T090010Z
LAST-MODIFIED:20241212T122237Z
UID:425-1737383400-1737390600@homecse.iitd.ac.in
SUMMARY:A Theory of Alternating Paths and Blossoms\, from the Perspective of Minimum Length
DESCRIPTION:Vijay V. Vazirani \, University of California\, Irvine. \nIt is well known that the proof of some prominent results in mathematics took a very long time — decades and even centuries. The first proof of the Micali-Vazirani (MV) algorithm\, for finding a maximum cardinality matching in general graphs\, was recently completed — over four decades after the publication of the algorithm (1980). MV is still the most efficient known algorithm for the problem. In contrast\, spectacular progress in the field of combinatorial optimization has led to improved running times for most other fundamental problems in the last three decades\, including bipartite matching and max-flow. \nThe new ideas contained in the MV algorithm\, and its proof remain largely unknown\, and hence unexplored. We hope to rectify this shortcoming and use ideas from the proof to give a simpler exposition of the algorithm. \nBased on this paper. \nBio: Vijay Vazirani is a distinguished professor at the University of California\, Irvine. A description of his research appears in the citation of his 2022 INFORMS John von Neumann Theory Prize. In 2001\, he published Approximation Algorithms\, which was followed by two co-edited books\, Algorithmic Game Theory in 2007 and Online and Matching-Based Market Design in 2023.
URL:https://homecse.iitd.ac.in/event/a-theory-of-alternating-paths-and-blossoms-from-the-perspective-of-minimum-length/
LOCATION:Bharti 501\, IIT Campus\, Hauz Khas\, New Delhi
CATEGORIES:Seminars
END:VEVENT
END:VCALENDAR