9 grudnia 2024 10:15
[Seminarium ZOK] Yongho Shin: "Online Correlated Selection"
This seminar talk is a gentle introduction on online correlated selection (OCS). In particular, a two-way OCS is an algorithm that, given a sequence of pairs arriving online, selects an element from each pair irrevocably, while ensuring some negative correlation between selections. This algorithmic framework was first introduced by the seminal work of Fahrbach, Huang, Tao, and Zadimoghaddam (FOCS 2020, JACM 2022) to obtain the first better-than-1/2-competitive algorithm for edge-weighted online bipartite matching with free disposal, and it has inspired many subsequent works, especially in the realm of online matching. However in this talk, we will only consider the classic unweighted online bipartite matching problem for simplicity.
In the first half of the talk, we will see a simple "two-choice" algorithm and show its 1/2-competitiveness through a primal-dual analysis. We will then present how a two-way OCS can improve the algorithm's performance. During the first half, we also expect to learn a mild implication on a lossless rounding scheme of two-choice algorithms for online bipartite matching.
The second half is dedicated to construction of some OCS algorithms. We will first present how Fahrbach et al.'s two-way OCS works and extend to a "three-way" OCS by having their two-way OCS as a building block. We will then see a major difficulty in analyzing this three-way OCS and how we circumvent this difficulty by adopting a good "surrogate" distribution.
Based on joint work with Hyung-Chan An (Yonsei University).