Tata Institute of Fundamental Research
A game theoretic proof of RANKING algorithm
STCS Student Seminar
Speaker:
Soumyajit Pyne
Date:
Friday, 12 Aug 2022, 16:00 to 17:00
Venue:
A201
(Scan to add to calendar)
Abstract:
Online Bipartitie Matching was first introduced by Karp, Vazirani and Vazirani (STOC’90). In their seminal paper they had inroduced the RANKING algorithm which admits a tight competitive ratio of 1-1/e. Since then multiple proofs of RANKING have been published. In this talk, we shall look at a simple Game Theoretic approach to proving the competitive ratio of RANKING, avoiding linear programming arguments. The proof is based on the paper by Eden, Feldman, Fiat and Segal (https://arxiv.org/abs/1804.06637).
| Speaker: | Soumyajit Pyne |
| Date: | Friday, 12 Aug 2022, 16:00 to 17:00 |
| Venue: | A201 |
(Scan to add to calendar)
Abstract:
Online Bipartitie Matching was first introduced by Karp, Vazirani and Vazirani (STOC’90). In their seminal paper they had inroduced the RANKING algorithm which admits a tight competitive ratio of 1-1/e. Since then multiple proofs of RANKING have been published. In this talk, we shall look at a simple Game Theoretic approach to proving the competitive ratio of RANKING, avoiding linear programming arguments. The proof is based on the paper by Eden, Feldman, Fiat and Segal (https://arxiv.org/abs/1804.06637).