Tata Institute of Fundamental Research
The online primal-dual method
STCS Student Seminar
Speaker:
Arghya Chakraborty (TIFR)
Organiser:
Shanthanu Suresh Rai
Date:
Friday, 26 Sep 2025, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
This talk will give a brief introduction to the online primal-dual method through the lens of online bipartite matching. We will begin with the classic online bipartite matching problem and discuss two well-known algorithms: RANKING and WATER-LEVEL. Using these as examples, we will explore how a primal-dual perspective can be used to analyze their performance. The focus will be on how the analysis can be carried out in an online fashion, highlighting a general approach that applies to a broad class of algorithms for online bipartite matching.
| Speaker: | Arghya Chakraborty (TIFR) |
| Organiser: | Shanthanu Suresh Rai |
| Date: | Friday, 26 Sep 2025, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
This talk will give a brief introduction to the online primal-dual method through the lens of online bipartite matching. We will begin with the classic online bipartite matching problem and discuss two well-known algorithms: RANKING and WATER-LEVEL. Using these as examples, we will explore how a primal-dual perspective can be used to analyze their performance. The focus will be on how the analysis can be carried out in an online fashion, highlighting a general approach that applies to a broad class of algorithms for online bipartite matching.