Tata Institute of Fundamental Research
Online Correlated Selection and related problems
Open Seminar
Speaker:
Arghya Chakraborty (TIFR)
Organiser:
Prahladh Harsha
Date:
Monday, 24 Jun 2024, 14:30 to 15:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Online Correlated Selection (OCS) is a novel online selection problem introduced by Matthew Fahrbach, Zhiyi Huang, Runzhou Tao, Morteza Zadimoghaddam to obtain improved online algorithm for thee dge-weighted bipartite matching problem. In this talk, I'll describe the OCS problem and describe an optimal algorithm for the 2-way OCS.We will then discuss extensions of the OCS problem as well as applications to the online edge-weighted bipartite matching problem.
| Speaker: | Arghya Chakraborty (TIFR) |
| Organiser: | Prahladh Harsha |
| Date: | Monday, 24 Jun 2024, 14:30 to 15:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Online Correlated Selection (OCS) is a novel online selection problem introduced by Matthew Fahrbach, Zhiyi Huang, Runzhou Tao, Morteza Zadimoghaddam to obtain improved online algorithm for thee dge-weighted bipartite matching problem. In this talk, I'll describe the OCS problem and describe an optimal algorithm for the 2-way OCS.We will then discuss extensions of the OCS problem as well as applications to the online edge-weighted bipartite matching problem.